LeetCode-Solution-Well-Explained

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

Cheap and reliable Node.js hosting starts at $3/month, and $1/month static HTML hosting

zdong1995 / LeetCode-Solution-Well-Explained

Programming Languages

Labels

Projects that are alternatives of or similar to LeetCode-Solution-Well-Explained

LeetCode-Solution-Well-Explained

Problems and Solutions