/LeetCode-Solution-Well-Explained

My LeetCode solutions using Java. Sorted in different topics and add detailed comments for easy understanding.

Primary LanguageJava

LeetCode-Solution-Well-Explained

java

Solutions for my LeetCode using Java. Sorted in different topics and add detailed comments for easy understanding.

Welcome to check my repository Algorithm-Interview to prepare for algorithm interview. This repo consists of beginer-friendly tutorial of Data Structure and Algorithm, summary of classified algorithm questions, and notes for Java and Object Oriented Design.

If this is helpful for you, please feel free to add a star to the repo. Thank you! ❤️

Problems and Solutions

# Title Topic Solution Basic idea Difficulty
1 two-sum HashTable Java Python One pass hashtable to check whether the complement in the map Easy
2 add-two-numbers LinkedList Java Two pointers to sum by digit, be careful with last non-zero carry after sum all digits Medium
3 longest-substring-without-repeating-characters Sliding Window Java Sliding window + HashTable counter to remove duplicates Medium
5 longest-palindromic-substring String Java Expand from 2n - 1 possible centers Medium
7 reverse-integer Other Java Check overflow to return 0 Easy
15 3sum Two Pointers Java For loop + Two Pointer to search for 2 Sum pair Medium
16 3sum-closest Two Pointers Java Two pointers to search 2 Sum pair equal to target - nums[i], maintain minDiff to determine closest Medium
17 letter-combinations-of-a-phone-number DFS Java DFS + using dictionary to handle possible letters of current number representation Medium
18 4sum Two Pointers Java Two times 2 Sum, guarantee the index of two pairs should be i1 < j1 < i2 < j2 to avoid duplicates Medium
19 remove-nth-node-from-end-of-list LinkedList Java Two pointer to mainatain a gap with size = n Medium
21 merge-two-sorted-lists LinkedList Java Maintain dummy head and tail to iteratively add smalled node to the end Easy
22 generate-parentheses DFS Java Check number of left / right parentheses before DFS. Medium
23 merge-k-sorted-lists LinkedList Java Use K-size min heap to compare k pointers to move the smallest node each time Hard
24 swap-nodes-in-pairs LinkedList Java Recursion rule swapPair(head.next.next) Medium
25 reverse-nodes-in-k-group LinkedList Java Find K-group, reverse K-group and link to next reversed sub-list. Hard
26 remove-duplicates-from-sorted-array Array Java Two pointers, slow is the last element to be returned. Easy
30 substring-with-concatenation-of-all-words Sliding Window Java Sliding window with unit of word, use two Map to compare whether matched Hard
33 search-in-rotated-sorted-array Binary Search Java Binary Search, each time we need to determine which part to search next, sorted or rotated sorted part Medium
34 find-first-and-last-position-of-element-in-sorted-array Binary Search Java Two times binary search to find start and end positions Medium
35 search-insert-position Binary Search Java Find closest and insert at the next position or closest position Easy
39 combination-sum DFS Java DFS each level represent how many we will select for each candidates Medium
40 combination-sum-ii DFS Java Subsets II problem, find unique subsets that sums to target Medium
41 first-missing-positive Array Java For the index i, swap the number nums[i] to its correct position, i.e. index = nums[i] - 1 Hard
42 trapping-rain-wate Two Pointers Java The water trapped at current index = max water level - current height. The max water level is determine by minimum between left and right max height Hard
45 jump-game-ii DP Java Array to store the min jumps needed to reach end from i-th position Hard
46 permutations DFS Java Use in-place swap or extra boolean array to mark used state. Medium
47 permutations-ii DFS Java For each level, use HashSet to track whether letter has been used. Medium
48 rotate-image Matrix Java Recursion to replace left top -> right top -> right bottom -> left bottom Medium
49 group-anagrams String Java Use count sort and hashmap to store each group of anagram Medium
50 powx-n Binary Search Java Recursive x^t = x^(t/2) * x^(t/2) and be careful with Interger.MIN_VALUE Medium
53 maximum-subarray DP Java Max between (previous max_sum + current num) and only current num itself Easy
54 spiral-matrix Matrix Java Iterative to traverse from top -> right -> bottom -> left, update begin index and end after each iteration Medium
55 jump-game DP Java Boolean array to store whether we can jump starting from current index to reach the end Medium
59 spiral-matrix-ii Matrix Java Recursion to fill matrix layer by layer, top row -> right col -> bottom row -> left col Medium
61 rotate-list LinkedList Java Find last (k % len + 1) node as newTail, reconnect list Medium
62 unique-paths DP Java Paths = paths from left + paths from right Medium
70 climbing-stairs DP Java ways to climb to i-th level = ways to climb to (i-1)th level + (i-2)th level Easy
72 edit-distance DP Java 2D array represent distance between two substring Hard
74 search-a-2d-matrix Binary Search Java 2D array to 1D array, Binary Search Medium
75 sort-colors Array Java Maintain 3 pointers to partition to 3 areas Medium
76 minimum-window-substring Sliding Window Java Maintain HashMap as counter of letters needed to match and update numToMatch when sliding the window Hard
77 combinations DFS Java Similar to all subsets, n levels recursion, base case need check size == k? Medium
78 subsets DFS Java For each level, two state: add to subset or not. Recursion tree will have num.length levels. Medium
80 remove-duplicates-from-sorted-array-ii Array Java Two pointers, each time check fast and (slow - 2) Medium
83 remove-duplicates-from-sorted-list LinkedList Java Iterative and recursive way to check duplicate and remove node Easy
84 largest-rectangle-in-histogram Stack Java Use one monotonic ascending stack to record the increasing sequencet. For the rectangle with height = current bar height: left bound is the index of previous bar in the stack, right bound is the index of first bar that smaller than stack top Hard
86 partition-list LinkedList Java Maintain two Dummy head and tail for small and large list, then concatenate Medium
88 merge-sorted-array Array Java In-place: two pointer from end to start, iteratively copy larger number to the end Easy
90 subsets-ii DFS Java Add element or not add element. If not add, skip all the rest duplicates. Medium
92 reverse-linked-list-ii LinkedList Java Find m-th node and record tail, reverse and connect 3 parts Medium
93 restore-ip-addresses DFS Java DFS with 3 branch, 4 level recursion tree, pruning for leading zero cases Medium
100 same-tree Tree Java Recursive compare LL & RL, LR & RR to determine whether is same tree for each pair Easy
101 symmetric-tree Tree Java Recursive compare LL & RR, LR & RL to determine whether symmetric for each pair Easy
102 binary-tree-level-order-traversal BFS Java BFS, use list to store value on each level Medium
103 binary-tree-zigzag-level-order-traversal BFS Java Use Deque to BFS and offerFirst/Last for odd/even layer respectively Medium
104 maximum-depth-of-binary-tree Tree Java Recursion to get max height from left and right child then increase by 1 Easy
105 construct-binary-tree-from-preorder-and-inorder-traversal Tree Java Find root from first position from pre-order array and find the index in in-order, to get the size of left subtree. Recursively build left subtree and left subtree Medium
106 construct-binary-tree-from-inorder-and-postorder-traversal Tree Java Find root from last position from pre-order array and find the index in in-order, to get the size of left subtree. Recursively build left subtree and left subtree Medium
110 balanced-binary-tree Tree Java Pre-order traverse and compare left & right using getHeight() helper function Easy
114 flatten-binary-tree-to-linked-list Tree Java Flatten left and right, then connect the tail of left to first node of right Medium
116 populating-next-right-pointers-in-each-node Tree Java Recursion or Iterative. Traverse the leftmost path, for each starting node, traverse the level using next pointer, to build next pointers for the next level Medium
117 populating-next-right-pointers-in-each-node-ii Tree Java BFS to level-order traversal. For each level, connect the current polled out node to the first node in the queue Medium
124 binary-tree-maximum-path-sum Tree Java For each node get path sum of left and right child. Update global max and return the larger path Hard
125 valid-palindrome Two Pointers Java Two pointers from left and right to compare digits and chars Easy
127 word-ladder BFS Java BFS starting from beginWord, each time check whether neighbor word in the dict, return shortest length once meet the endWord Medium
128 longest-consecutive-sequence Two Pointers Java Use set to speed up search process, for each number in the array, use as a center of sequence, and expand to left and right to find the longest length Hard
133 clone-graph Graph Java DFS + Map to store 1:1 mapping of original node and copied node Medium
136 single-number Bits Manipulation Java a XOR a = 0 thus XOR all the elements and the duplicates will cancel to 0, only single number left Easy
137 single-number-ii Bits Manipulation Java For each bits, find the number of 1 bits and mod 3 to find whether the current bit of single number is 1 Medium
138 copy-list-with-random-pointer LinkedList Java Maintain 1 to 1 mapping from orignal node to copied node to avoid duplicate copy Medium
139 word-break DP Java DP table to store whether the substring [0, i) can break Medium
141 linked-list-cycle LinkedList Java Fast and slow pointer, cycle exists when two pointers meet Easy
143 reorder-list LinkedList Java Find mid nodes -> Reverse second part -> Merge two parts Medium
144 binary-tree-preorder-traversal Tree Java Recursion + Iterative by explicitly maintain a stack Medium
147 insertion-sort-list LinkedList Java Use dummy node, each time find the last position that is smaller than current node, then insert current to that position Medium
151 reverse-words-in-a-string String Java 3-steps reverse and remove space Medium
153 find-minimum-in-rotated-sorted-array Binary Search Java Find the first element that <= last element Medium
155 min-stack Stack Java Auxiliary sync stack to store min, push min when num <= min Easy
156 binary-tree-upside-down Tree Java Subproblem: Reverse tree with root of curRoot.left Medium
159 longest-substring-with-at-most-two-distinct-characters Sliding Window Java Sliding window and maintain HashMap with count representing types of unique characters in current window Medium
160 intersection-of-two-linked-lists LinkedList Java Get length of two linkedlist, move the shorter one by diff length, use two pointers to find the intersection Easy
167 two-sum-ii-input-array-is-sorted Two Pointers Java Two pointers from left and right Easy
170 two-sum-iii-data-structure-design Design Java Add: put to HashMap -> O(1), Find: iterate each key in HashMap and find 2 sum -> O(N) Easy
186 reverse-words-in-a-string-ii String Java 3-steps reverse: reverse all words, then reverse whole sentence Medium
189 rotate-array Array Java 3-steps reverse, first part ending at (length - 1 - steps). Easy
190 reverse-bits Bits Manipulation Java swap left and right by using left shifted mask Easy
191 number-of-1-bits Bits Manipulation Java Iteratively right shift and compare n & 1 with 1 Easy
199 binary-tree-right-side-view Tree Java DFS: traverse root -> right -> and record the first node reaching level i. BFS: level order traverse + record last node in current level Medium
200 number-of-islands Graph Java BFS/DFS Traverse each grid and mark visited Medium
203 remove-linked-list-elements LinkedList Java Dummy node, iteratively remove all target Easy
206 reverse-linked-list LinkedList Java Iterative and Recursion Easy
209 minimum-size-subarray-sum Array Java Sliding window, shrink subarray window when sum >= s Medium
215 kth-largest-element-in-an-array Heap Java MinHeap with size k / MaxHeap with size n / Quick Selection Medium
216 combination-sum-iii DFS Java Find k size subsets from [1,2,3,4,5,6,7,8,9] that sums to n Medium
226 invert-binary-tree Tree Java Pre-order/Post-order recursion/iterative or level-order iterative to traverse the tree to invert left and right Easy
231 power-of-two Bits Manipulation Java Check whether contain only one 1-bit Easy
234 palindrome-linked-list LinkedList Java Find mid -> reverse 2nd half -> check palindrome Easy
235 lowest-common-ancestor-of-a-binary-search-tree Tree Java If root.val is between p.val and q.val, then root is the LCA Easy
236 lowest-common-ancestor-of-a-binary-tree Tree Java For each level, return root when find p and q in the left or right subtree, otherwise, return left child or right child that is p or q Medium
237 delete-node-in-a-linked-list LinkedList Java Replace current node to next node, then delete next node to mimic deleting current node Easy
240 search-a-2d-matrix-ii Binary Search Java Binary Search starting from the left bottom corner, find the largest smaller than target to search right side of row, find the first larger than target to search upside of col Medium
242 valid-anagram String Java Increase count when traverse source string, while decrease for target. Check whether negative count exists Easy
254 factor-combinations DFS Java Find all factors and backtracking similar to coin change Medium
259 3sum-smaller Two Pointers Java Fix one number, use Two Pointers to run 2 sum smaller Medium
268 missing-number Bits Manipulation Java XOR all the numbers Easy
283 move-zeroes Array Java 2 pointers copy non-0s to front of left, then fill left to end with 0s. Easy
286 walls-and-gates BFS Java Starting from all the GATEs, using BFS to expand circle to update shortest distance to each INF Medium
317 shortest-distance-from-all-buildings BFS Java Run BFS starting from each building to update cost to each land, exclude unreachable lands each time to speed up the search algorithm Hard
322 coin-change DP Java DP[i] = DP[i - coin] + 1, represent number of coins needed to change Medium
328 odd-even-linked-list LinkedList Java Similar to partition linkedlist, use index to determine odd or even Medium
340 longest-substring-with-at-most-k-distinct-characters Sliding Window Java Sliding window and maintain HashMap with count representing types of unique characters in current window Medium
344 reverse-string String Java Two pointers swap or Recursion Easy
347 top-k-frequent-elements Heap Java HashMap for counter, MinHeap to scan the whole keys of counter Medium
374 guess-number-higher-or-lower Binary Search Java Classical binary search Easy
378 kth-smallest-element-in-a-sorted-matrix BFS Java Best First Search, initial at [0][0], expand each node to generate [x+1][y] and [x][y+1] Medium
387 first-unique-character-in-a-string String Java HashMap to store counter and one pass to find first character with count = 1 Easy
394 decode-string Stack Java 2 stack for count and cur string, decode when meet "]" Medium
409 longest-palindrome String Java HashMap/Set/Array to store count and then find the number of characters appeared odd times Easy
417 pacific-atlantic-water-flow BFS Java Two BFS starting from Pacific and Atlantic ocean to find reachable cells, find the overlap will be the result Medium
419 partition-equal-subset-sum DP Java All Subsets similar DFS + Memoization Medium
430 flatten-a-multilevel-doubly-linked-list LinkedList Java For each node that has child, traverse child list to find tail and connect Medium
433 minimum-genetic-mutation BFS Java BFS to search the shortest length from begin to end, the result should be length - 1 Medium
438 find-all-anagrams-in-a-string Sliding Window Java Sliding window and maintain hashmap to count the number of letters needed to match. When satisfied, check window length == target length and add to result Medium
443 string-compression String Java Slow and fast pointers to read and copy chars and counts Easy
461 hamming-distance Bits Manipulation Java XOR the two Interger and count how many 1-bits Easy
509 fibonacci-number DP Java 2-value Memoization fibo(N) = fibo(N-2) + fibo(N-1) Easy
542 01-matrix BFS Java Starting from each 0 to find the shortest distance to 1 Medium
554 brick-wall HashTable Java Use hashtable to counter the number of bricks at each length as edge. Use prefix sum to find the edge position Medium
572 subtree-of-another-tree Tree Java Traverse the tree to check whether the subtree at each node are the same tree as target tree Easy
611 valid-triangle-number Two Pointers Java Fix long side and number of two sum pairs that larger than the longer side Medium
617 merge-two-binary-trees Tree Java Recursion to merge left and right to connect to current root Easy
643 maximum-average-subarray-i Array Java Sliding window to find the maximum sum with size K Easy
647 palindromic-substrings String Java Expand from each possbile centers Medium
653 two-sum-iv-input-is-a-bst Tree Java Maintain a set to record the seen elements during traverse, check whether complement of current root in set Easy
654 maximum-binary-tree Tree Java Scan [left, right] each time to find the maximum value and index to build root, then recursively build left subtree in [left, rootIdx - 1] and right subtree in [rootIdx + 1, right] Medium
658 find-k-closest-elements Binary Search Java Find closest and expand to both sides Medium
674 longest-continuous-increasing-subsequence DP Java dp[i] represents the longest increasing subarray in [0, i], increment by 1 when still ascending, otherwise reset current dp to 1 Easy
680 valid-palindrome-ii Two Pointers Java Two Pointers, if character at left and right are different, check whether remove-left or remove-right is palindrome Easy
692 top-k-frequent-words Heap Java Use HashMap to count the frequency and use maxHeap to poll top K Medium
694 number-of-distinct-islands Graph Java DFS to find the islands and record the direction path string, in order to discriminate islands Medium
695 max-area-of-island Graph Java DFS to search the area through four direction and return the sum to obtain area of island Medium
698 partition-to-k-equal-sum-subsets DFS Java Repeatedly DFS k times to find K subsets with sum equal to SUM/K Medium
700 search-in-a-binary-search-tree Tree Java Iterative and Recursive Easy
702 search-in-a-sorted-array-of-unknown-size Binary Search Java Reversely run binary search to find the right bound, then classical binary search Medium
703 kth-largest-element-in-a-stream Heap Java Maitan a minHeap to scan the whole stream. If new elment > peek, poll and offer new element. Easy
704 binary-search Binary Search Java Classical Binary Search Easy
724 find-pivot-index Array Java Increase prefix sum to reach half of total sum Easy
744 find-smallest-letter-greater-than-target Binary Search Java Find first element that larger than target Easy
763 partition-labels Two Pointers Java One pass to record the last index of each character. Two pointers to scan the string, extend current partition when met new character. Medium
780 reaching-points Other Java Reverse backtracking to consider two operations recursively Hard
785 is-graph-bipartite Graph Java BFS each node and color the node, if current node and neighbors have same color, return false Medium
786 k-th-smallest-prime-fraction Heap Java Implicit fraction matrix composed by given sorted array. Use heap to find K-th smallest. Hard
819 most-common-word String Java One pass to manipulate the char array to maintain the max counter string Easy
876 middle-of-the-linked-list LinkedList Java Fast & Slow two pointers Easy
889 construct-binary-tree-from-preorder-and-postorder-traversal Tree Java Find root and left subtree root from 1st and 2nd in pre-order sequence, get the left size and recursively construct left and right subtree Medium
895 maximum-frequency-stack Design Java Use one map to maintain the frequency for each element, use another map to map each frequency to a stack containing all element with the same frequency, update maxFreq if applicable Hard
905 sort-array-by-parity Two Pointers Java Left and Right pointer, swap when left is odd and right is even Easy
912 merge-sort Array Java Recursion helper function + merge two sorted array Medium
912 quick-sort Array Java Pick random pivot + maintain two pointer to partion the array Medium
912 selection-sort Array Java Maintain one partition between sorted part and unsorted part Medium
951 flip-equivalent-binary-trees Tree Java Recursively check each subtree is symmetric tree or identical tree Medium
958 check-completeness-of-a-binary-tree BFS Java BFS level order traversal, add one bool to indicate whether null found in the leftside Medium
973 k-closest-points-to-origin Heap Java maxHeap to scan the point list Medium
981 time-based-key-value-store HashTable Java Use TreeMap to keep order of timestamp for value of each key Medium
1010 pairs-of-songs-with-total-durations-divisible-by-60 Array Java 2 Sum to find the number of remainder (time % 60) pairs that sums to 60 Medium
1047 remove-all-adjacent-duplicates-in-string String Java Two pointer to maintian one in-place stack. Easy
1089 duplicate-zeroes Two Pointers Java One pass count zeroes, then two pointers from right to left to copy elements Easy
1120 maximum-average-subtree Tree Java Each left get subtree sum and node number from left and right child, then calculate average and update global max Medium
1209 remove-all-adjacent-duplicates-in-string-ii String Java Count array + fast/slow pointers implicitly mainatain as stack to pop k duplicates Medium
1396 design-underground-system Design Java Two HashMap for user-checkin and routes-time Medium
1428 leftmost-column-with-at-least-a-one Matrix Java Startign from bottom right, search left we met 1 to find leftmost 1, search up when met 0 Medium
1608 special-array-with-x-elements-greater-than-or-equal-x Binary Search Java Binary Search to find the first position nums[i] >= len - i and nums[i - 1] < len - u Easy
1644 lowest-common-ancestor-of-a-binary-tree-ii Tree Java If LCA is p, we need to check whether q appeared in the subtree of p, vice versa Medium
1650 lowest-common-ancestor-of-a-binary-tree-iii Tree Java Find intersection of two linkedlist, parent is like next pointer Medium
1662 check-if-two-string-arrays-are-equivalent String Java Two pointers to move across different strings, move string index when char index reach end Easy
1663 smallest-string-with-a-given-numeric-value Array Java Greedy to make left side as small as possbile, thus rightside should be as large as possbile Medium
1664 ways-to-make-a-fair-array Array Java After remove nums[i], the even sum at right of i will become odd sum and the odd sum at right of i will become even sum Medium
L8 rotate-string String Java 3 steps reverse, divided by index str.length - 1 - offset Easy
L11 search-range-in-binary-search-tree Tree Java inOrder traverse and check bound condition before recurse left or right Medium
L14 first-position-of-target Binary Search Java Classical binary search + right = mid when found target to search left-side + post-processing Easy
L39 recover-rotated-sorted-array Array Java 3 Steps reverse. One pass to find offset Easy
L229 stack-sorting Array Java Selection sort. Bottom of buffer stack are sorted elements. Medium
L443 two-sum-greater-than-target Two Pointers Java Two Pointer, count pairs when left + right > target Medium
L458 last-position-of-target Binary Search Java Classical binary search + left = mid when found target to search right-side + post-processing Easy
L459 closest-number-in-sorted-array Binary Search Java Classical binary search + post-processing to compare distance from left/right to target Easy
L470 tweaked-identical-binary-tree Tree Java Recursion check whether is symmetric or same tree Medium
L533 two-sum-closest-to-target Two Pointers Java Two pointers and update minDiff each time Medium
L587 two-sum-unique-pairs Two Pointers Java Sort + Two Pointers, need to skip duplicate number Medium
L609 two-sum-less-than-or-equal-to-target Two Pointers Java Two Pointer, count pairs when left + right <= target Medium
L610 two-sum-difference-equals-to-target Two Pointers Java Two pointer sliding window and make sure left < right Medium
L686 remove-arbitrary-space String Java Two pointers to copy non-space chars to slow position. Add heading space to non-first words. Easy