Skip to content

Latest commit

 

History

History
1036 lines (847 loc) · 115 KB

README.md

File metadata and controls

1036 lines (847 loc) · 115 KB

Contents

Tag Questions


Concurrency

SQL


Array / String

General cases we want to replace element with non-repeating element in nums, so we set an index to keep track of repeating position.

Array / String
LeetCode 150
88. Merge Sorted Array Easy Link Meta Tag Compare nums1, nums2 backward and add the larger value into the end of nums1, use three pointers to keep track
27. Remove Element Easy Link Use pointer to keep track of non-val element and replace the index when i != val to remove the val in nums
26. Remove Duplicates from Sorted Array Easy Link Similar to 27, keep track of prev elem, if current n != prev, replace nums[k] = n, update prev = n
80. Remove Duplicates from Sorted Array II Medium Link
169. Majority Element Easy Link Use two variables to keep track of curMax element and its count, decrement count if current elem != val, when count == 0, update curMax = i. Otherwise, increment count
189. Rotate Array Mediun Link Reverse nums and reverse nums[:k], same as rotate the array to the right by k steps
121. Best Time to Buy and Sell Stock Easy Link Keep track of mini and maxi
122. Best Time to Buy and Sell Stock II Medium Link Similar to 121
45. Jump Game II Medium Link Use l, r ptrs to find a reachable range, update farthest variable within the range, update l = r + 1, r = farthest, update jumps by 1
14. Longest Common Prefix Easy Link
58. Length of Last Word Easy Link
151. Reverse Words in a String Medium Link
42. Trapping Rain Water Hard Link Use l, r pointers to update maxLeft, maxRight, update res += maxLeft - height[l] or by maxRight, then we update maxLeft, maxRight to a greater value from height[l], height[r]
6. Zigzag Conversion Medium Link Find the distance to get another char on the same row. Use the normal interval - (current row * 2) to get the extra char on each interval
68. Text Justification Hard Link For each row with maxWidth, repeatly add words until a new word cannot be added. Then we compute how many spaces we need to assign after each word
1380. Lucky Numbers in a Matrix Easy Link Cisco
274. H-Index Medium Link Sort citations in descending order, find when index >= citation, or return len(citations) in the end
13. Roman to Integer Easy Link
12. Integer to Roman Medium Link
28. Find the Index of the First Occurrence in a String Easy Link Brute Force to try each haystack[i:i + len(needle)] == needle
380. Insert Delete GetRandom O(1) Medium Link
135. Candy Hard Link Similar to 238, initialize an array and traverse from left to right and right to left to compare their neighbor, and update res[i] accordingly
Blind 75
217. Contains Duplicate Easy Link
1. Two Sum Easy Link Amazon, Meta Save the remainder (target - nums[i]) into hashmap, when a remainder exists in hashmap, return [i, hashmap[nums[i]]]
347. Top K Frequent Elements Medium Link Amazon, Meta Tag Count num with their counts, use minHeap to sort the counts then append num k times from minHeap to res[]
692. Top K Frequent Words Medium Link Amazon
271. Encode and Decode Strings Medium Link
238. Product of Array Except Self Medium Link Maintain a list of left product, then traverse from right to left update with product, and update product * nums[i]
128. Longest Consecutive Sequence Medium Link Convert nums to set() to avoid duplicate elements, then for each base element (check if n-1 in set), we increment by 1 each time when the total is in the set()
LeetCode 75
1768. Merge Strings Alternately Easy Link Meta Use two ptrs to add chars from two strings alternatively, then check to add the remaining from word1 or word2
1071. Greatest Common Divisor of Strings Easy Link
1431. Kids With the Greatest Number of Candies Easy Link Easy Not worthy to redo
605. Can Place Flowers Easy Link Meta Append 0 to two ends of flowerbed, check flowerbed[i] and its neighbors are all 0 or not, if so, replace 0 to 1 and decrement n. Return n <= 0
345. Reverse Vowels of a String Easy Link
334. Increasing Triplet Subsequence Medium Link
443. String Compression Medium Link
Miscellaneous
179. Largest Number Medium Link Google OA
1827. Minimum Operations to Make the Array Increasing Easy Link Google OA
1526. Minimum Number of Increments on Subarrays to Form a Target Array Hard Link Google OA
3024. Type of Triangle Easy Link Google Tag
2663. Lexicographically Smallest Beautiful String Hard Link Google Tag Increment the last element and check if current element within range of k letters, iterate to the left and make changes if needed
1652. Defuse the Bomb Easy Link Use curr % len(code) to get the next k numbers, increment curr k times. Use len(code) + curr % len(code) to get previous k numbers, decrement curr k times
408. Valid Word Abbreviation Easy Link Meta Tag Use pointer for each string to compare, if abbr[j].isdigit(), we extract the number and increment i += int(number)
1570. Dot Product of Two Sparse Vectors Medium Link Meta Tag Use hashmap to save nonzero element with its index as key to hashmap{}. Update res with an index exists in both hashmaps
791. Custom Sort String Medium Link Meta Use hashmap to save each char in s with counts, traverse order and add char in hashmap with repeated times to res, traverse hashmap to add missing chars to res
1762. Buildings With an Ocean View Medium Link Meta Traverse heights from right to left, save the last height as curMax, if heights[i] > curMax, update curMax and save its index into res[], finally, return the reversed res[]
921. Minimum Add to Make Parentheses Valid Medium Link Meta Count "(" and ")", when encounter ")", check if we have "(" to remove or decrement, otherwise, increment the count of ")".
65. Valid Number Hard Link Meta Keep track of seenDigit, seenExponent, seenDot, then we check if the current char is valid base on some rules
415. Add Strings Easy Link Meta Use two ptrs to access two chars backward + carry to perform addition, and append the result to []
287. Find the Duplicate Number Medium Link Fast and Slow method
31. Next Permutation Medium Link Meta Find index such that nums[i] < nums[i+1], then find another element nums[j] > nums[i] from backward, swap them, and reverse nums[i+1:]
3043. Find the Length of the Longest Common Prefix Medium Link Uber OA Use hashset to save all the prefixes of x from arr1, and compare each prefixes of y from arr2
3151. Special Array I Easy Link Use prev to keep track previous parity and check if it matches the current parity
1800. Maximum Ascending Subarray Sum Easy Link Kadane's Algorithm, when a non-ascending element exists, reset curSum = 0
1790. Check if One String Swap Can Make Strings Equal Easy Link Use two variables to keep track of the difference indices, only counts == 0 or 2 are possible for the swap
767. Reorganize String Medium Link Amazon Tag Count the frequency of each char and use maxHeap to alternate placing the most frequent chars
3461. Check If Digits Are Equal in String After Operations I Easy Link Repeatly update s until len(s)==2, then compare if the first and the second strings are equal
2873. Maximum Value of an Ordered Triplet I Easy Link Daily Question Brute Force so far

Two Pointers

Two pointers can save space complexity, because it only uses constant space complexity $O(1)$. Usually use l, r pointers and either increment l or decrement r depends on the current sum compare with target value.

Two Pointers
LeetCode 150
125. Valid Palindrome Easy Link Meta Tag Use l, r ptrs to compare if two elem are the same, increment or decrement ptr if non-alphanumeric elem exists
167. Two Sum II - Input Array Is Sorted Medium Link
42. Trapping Rain Water Hard Link
15. 3Sum Medium Link
LeetCode 75
283. Move Zeroes Easy Link
392. Is Subsequence Easy Link
11. Container With Most Water Medium Link
1679. Max Number of K-Sum Pairs Medium Link
Miscellaneous
5. Longest Palindromic Substring Medium Link Amazon, Cisco Use l, r ptrs to compare if s[l] == s[r] to confirm palindrome, update res with longer substring
1268. Search Suggestions System Medium Link
680. Valid Palindrome II Medium Link Meta Tag Use two ptrs to find where two chars are different, then check if s[l+1, r] or s[l, r-1] is a valid palindrome

Sliding Window

Sliding Window technique is similar to Two Pointers, usually use a left pointer as a "Pivot" to know where we start recently and then update left += 1. Sometimes we may need to use hashmaps to find substring.

Sliding Window
LeetCode 150
209. Minimum Size Subarray Sum Medium Link Maintain a sliding window with curSum, while curSum >= target, we update res = min(res, r - l + 1) and shrink the sliding window to find the minimal length subarray
3. Longest Substring Without Repeating Characters Medium Link Maintain a sliding window, repeatedly update the length when there is no repeated character. When a repeated char exists, shrink the sliding window from the left-most element
30. Substring with Concatenation of All Words Medium Link
76. Minimum Window Substring Hard Link Meta Use two hashmaps and 2 counts to keep track of every chars, update res when sCount == tCount, and we start shrinking the sliding window
LeetCode 75
643. Maximum Average Subarray I Easy Link First calculate the sum(nums[:k]) as sliding window result, then update the curSum by removing the left most element and adding the new element
1456. Maximum Number of Vowels in a Substring of Given Length Medium Link
1493. Longest Subarray of 1's After Deleting One Element Medium Link Similar to 487
1004. Max Consecutive Ones III Medium Link Meta Maintain sliding window with at most k 0, each time if nums[r] is 0, we decrement k, when k is negative, we update l += 1, same as moving the current max sliding window to the right each time
NeetCode 150
121. Best Time to Buy and Sell Stock Easy Link
424. Longest Repeating Character Replacement Medium Link
567. Permutation in String Medium Link
239. Sliding Window Maximum Hard Link
Miscellaneous
53. Maximum Subarray Medium Link
485. Max Consecutive Ones Easy Link
487. Max Consecutive Ones II Medium Link Similar to 1493
3318. Find X-Sum of All K-Long Subarrays I Easy Link Google Tag Sliding Window, maxHeap, hashmap
2461. Maximum Sum of Distinct Subarrays With Length K Medium Link Sliding window to find max sum of subarray, use hashmap to detect duplicate elements
1358. Number of Substrings Containing All Three Characters Medium Link Daily Question Maintain a valid sliding window, then count how many extra char we can add. Then shrink the sliding window to be invalid, repeat

Matrix

The trick is to use pointers to keep in track of the boundaries. Then we shrink the boundaries after we finish a traverse or something.

Matrix
36. Valid Sudoku Medium Link Meta Use three dicts to check repetition
54. Spiral Matrix Medium Link Use four variables l, r, t, b to process in four directions l->r, t->b, r->l, b->t
48. Rotate Image Medium Link
73. Set Matrix Zeroes Medium Link
289. Game of Life Medium Link Traverse the grid to find which entries need to be changed later, and we mark it as other number. Later, we change the marked number back to either live or dead
Miscellaneous
1861. Rotating the Box Medium Link First move all the stones to the valid spaces, then convert each column into each row of the new matrix
498. Diagonal Traverse Medium Link Meta Save the diagonal index by (r+c) with values {diagonal_idx: [val]}, then check idx % 2 to decide whether reverse the saved values' list or not
766. Toeplitz Matrix Easy Link Meta Compare each entry with their bottom-right neighbor (if exists)
37. Sudoku Solver Medium Link Meta Use 3 sets to save existed vals, backtrack number i from [1, 9] for '.'
59. Spiral Matrix II Medium Link AutoX Tag Similar to 54. Spiral Matrix, use four variables l, r, t, b to proceed four directions fill in
311. Sparse Matrix Multiplication Medium Link AutoX Tag

Binary Search

Use this method when we see sorted in non-decreasing order or when we need to write an algorithm in $O(log\ n)$ runtime. Use left & right pointer, then we iteratively find the mid point by (left + right) // 2, and compare the mid point with target, if target < m, we update the right by m - 1, if target > m, we update left by m + 1.

Binary Search
LeetCode 150
704. Binary Search Easy Link
35. Search Insert Position Easy Link
74. Search a 2D Matrix Medium Link
153. Find Minimum in Rotated Sorted Array Medium Link
33. Search in Rotated Sorted Array Medium Link
162. Find Peak Element Medium Link Meta Tag Run Binary Search to check if a peak element exists, if not, update l or r pointer to the greater value neighbor
34. Find First and Last Position of Element in Sorted Array Medium Link Meta Find the left end and right end of nums by running Binary Search twice, update different ptr each time
4. Median of Two Sorted Arrays Hard Link
LeetCode 75
374. Guess Number Higher or Lower Easy Link
2300. Successful Pairs of Spells and Potions Medium Link Sort potions first and then run Binary Search on potions to find the smallest left pointer for each spell
875. Koko Eating Bananas Medium Link Run Binary Search on range of speed k, update r = k - 1 when hours <= h, update l = k + 1 when hours > h
Miscellaneous
528. Random Pick with Weight Medium Link Meta Tag First initialize each index from [0, len(w)-1] a probability by w[i] / sum(w), then we calculate the prefixSum of each index. Next, randomly generate a prob within [0, 1], then we use Binary Search to find the index with the closest probability
1539. Kth Missing Positive Number Easy Link Meta Run Binary Search with k on the difference between the original arr and current arr
2529. Maximum Count of Positive Integer and Negative Integer Easy Link Daily Question Use Binary search to find the begin and end of 0 to determine the number of positive ints and negative ints
3356. Zero Array Transformation II Medium Link Daily Question Use Binary Search to find the minimum number of queries we need by creating difference array and compare prefixSum with each element in nums
2226. Maximum Candies Allocated to K Children Medium Link Daily Question Run Binary search on [1,max(candies)], calculate if current m candies can be allocated to K children, then update l, r accordingly
2560. House Robber IV Medium Link Daily Question Run Binary Search on range [1, max(nums)] and loop over nums to compare with nums[m] we find, if the num of houses we can rob >=k, update r=m-1, otherwise, update l=m+1
2594. Minimum Time to Repair Cars Medium Link Daily Questioin Run Binary Search on [1, min(ranks)*car^2] by the formula, then count the total cars can be repaired under different rank, and update l, r accordingly

Backtracking

Backtracing is recursion with base case(s), we have to first find the base case(s), if the case satisfies the base case condition that we can append the desired answer then return, and continue the recursion by i+1.

Backtracking
78. Subsets Medium Link Meta Use backtrack with index i to keep track of current curSum[], when i==len(nums), we append curSum into res[] and return, we pop the last element and add new element into curSum with i += 1
90. Subsets II Medium Link
39. Combination Sum Medium Link
40. Combination Sum II Medium Link
216. Combination Sum III Medium Link
17. Letter Combinations of a Phone Number Medium Link Use index i to traverse each digit in the digitsMap, when len(string) == len(digits), add this to res[], increment index i
77. Combinations Medium Link
22. Generate Parentheses Medium Link
46. Permutations Medium Link backtrack from each element to form permutation with unvisited elements
79. Word Search Medium Link
131. Palindrome Partitioning Medium Link
51. N-Queens Hard Link
52. N-Queens II Hard Link
386. Lexicographical Numbers Medium Link Google Tag Similar to combination
Miscellaneous
698. Partition to K Equal Sum Subsets Medium Link Meta Use Backtrack to try each element with other elements subarray, if the subarray equals to k, we mark all elements to be visited, run backtrack from the beginning again. For every subarray, we decrement k -= 1, return True when k == 0
1079. Letter Tile Possibilities Medium Link Save each char's frequency into list of 26 chars, each time we use 1 char, reduce the count in list, then run backtrack with this list to count

Stack

Stack
LeetCode 150
20. Valid Parentheses Easy Link AutoX Tag
71. Simplify Path Medium Link Meta Tag Detect each char to know if it equals to '/' or not, and use stack to add new file name or pop previous file name
155. Min Stack Medium Link
150. Evaluate Reverse Polish Notation Medium Link
224. Basic Calculator Hard Link Google Tag, Meta Tag Use res, sign ,curr to keep track of previous operation result, update res when we have new sign, append res, sign into stack[] when we have "(". Calculate result within (), and pop everything back from stack[], reset variables
LeetCode 75
2390. Removing Stars From a String Medium Link Use stack to store each element until a "*", we then pop the top of stack to remove "*"s left non-star character
735. Asteroid Collision Medium Link
394. Decode String Medium Link Google Tag
NeetCode 150
22. Generate Parentheses Medium Link
84. Largest Rectangle in Histogram Hard Link Google Tag
Miscellaneous
1249. Minimum Remove to Make Valid Parentheses Medium Link Meta Tag Use stack to save "(" index, when we encounter ")", we pop the last index from stack to close a parenthese. If we encounter ")" with no "(", change it to ""
227. Basic Calculator II Medium Link Meta Tag Use stack to save previous result, we only append new element with sign into stack when we encounter a new sign
921. Minimum Add to Make Parentheses Valid Medium Link Meta Count "(" and ")", when encounter ")", check if we have "(" to remove or decrement, otherwise, increment the count of ")".

Monotonic Stack

Monotonic Stack
LeetCode 75
739. Daily Temperatures Medium Link Maintain a decreasing monotonic stack and update prev less temperature's index with day difference
901. Online Stock Span Medium Link Maintain an decreasing monotonic stack, when current price >= last elem in stack, add its span with current span, eventually append [price, span] into stack

Linked List

Usually needs to check if not node: return None

Linked List
141. Linked List Cycle Easy Link
21. Merge Two Sorted Lists Easy Link
2. Add Two Numbers Medium Link Meta Create dummy node with carry to save the sum
92. Reverse Linked List II Medium Link
138. Copy List with Random Pointer Medium Link Meta Use hashmap to save each node with new node, traverse head to assign .next, .random to be the new node in hashmap
143. Reorder List Medium Link
19. Remove Nth Node From End of List Medium Link
146. LRU Cache Medium Link Meta Use two dummy nodes to keep track of the LRU and MRU, if we need to remove the LRU, remove right.prev. Insert to left.next to add new node. Access value by hashmap[key].val
25. Reverse Nodes in k-Group Hard Link
61. Rotate List Medium Link Python, C++
23. Merge k Sorted Lists Hard Link Meta Merge 2 lists each time and replace lists with the merged sorted lists
LeetCode 75
2095. Delete the Middle Node of a Linked List Medium Link Fast, Slow method to remove the middle node
328. Odd Even Linked List Medium Link Create odd and even linkedlist, add even linked list to the end of odd linkedlist
206. Reverse Linked List Easy Link Flip every node to connect its previous node, and reset prev, head every time
2130. Maximum Twin Sum of a Linked List Medium Link Reverse the first half linked-list, update res with the first half.val + second half.val
LeetCode 150
86. Partition List Medium Link Use two nodes to save lists of nodes less than x and nodes greater or equal to x
Miscellaneous
83. Remove Duplicates from Sorted List Easy Link Repeatly set curr.next = curr.next.next to remove duplicate, update curr only a non-duplicated element is found
82. Remove Duplicates from Sorted List II Medium Link Use while loop to skip duplicate (while head and head.next and head.val == head.next.val), use prev node to save the non-duplicate element
708. Insert into a Sorted Circular Linked List Medium Link Meta Use prev, curr to keep track of two nodes and compare their values with insertVal and add new Node between prev and curr

Binary Tree General

Binary Tree Problems usually can use Recursion to solve, start from the root, then recurse on its left subtree and right subtree to check three conditons: 1. if not left and not right (when both are None). 2. if not left or not right (when one of the node is None, not match). 3. if left.val != right.val (values are not the same, not match).

It is also convention to use BFS (queue), DFS (stack) to check each node with the above three conditions.

Binary Tree General
LeetCode 150
104. Maximum Depth of Binary Tree Easy Link DFS
100. Same Tree Easy Link
226. Invert Binary Tree Easy Link
101. Symmetric Tree Easy Link
105. Construct Binary Tree from Preorder and Inorder Traversal Medium Link
106. Construct Binary Tree from Inorder and Postorder Traversal Medium Link
117. Populating Next Right Pointers in Each Node II Medium Link Run BFS on each level and set each node's next to the next node, except the last one
114. Flatten Binary Tree to Linked List Medium Link Find curr's left subtree's rightmost node and set its node.right to curr's right-subtree. Then set curr.right = curr.left, update curr.left = None and curr = curr.right
173. Binary Search Tree Iterator Medium Link Use stack[] to save nodes in descending order, so we can always find the next smallest value by popping
222. Count Complete Tree Nodes Easy Link
112. Path Sum Easy Link Run DFS from root to leaf, check if curSum == targetSum
124. Binary Tree Maximum Path Sum Hard Link
987. Vertical Order Traversal of a Binary Tree Hard Link Meta Save (node, row, col) into deque[], and run BFS to append node.left with (row+1, col-1) and node.right with (row+1, col+1). Add all nodes with the same col into hashmap{col: [node.val]}. Sort col and row in the end
Miscellaneous
889. Construct Binary Tree from Preorder and Postorder Traversal Medium Link Find the left-root accordingly from preorder and find offset of how many nodes to be included in the left-subtree, then recursively build tree

Binary Tree BFS

BFS uses collections.queue() and follows FIFO, DFS uses stack() and follows LIFO, both BFS and DFS can be implemented by list().

Binary Tree BFS
199. Binary Tree Right Side View Medium Link Meta Tag Run BFS on each level and only append the last node of each level to res[]
637. Average of Levels in Binary Tree Easy Link
102. Binary Tree Level Order Traversal Medium Link
103. Binary Tree Zigzag Level Order Traversal Medium Link
LeetCode 75
1161. Maximum Level Sum of a Binary Tree Medium Link Similar to 199, standard BFS with slightly modification
Miscellaneous
314. Binary Tree Vertical Order Traversal Medium Link Meta Run BFS to save all the nodes with their column index [node, col] into deque and save them into hashmap {index: [node]}
863. All Nodes Distance K in Binary Tree Medium Link Meta Build an undirected graph to connect two connected nodes together, then run BFS from target to add all its neighbor nodes into deque, when distance == k, we append the node.val into res[]
958. Check Completeness of a Binary Tree Medium Link Meta Run BFS with seenNull to check if a null node exists, if it exists and we have other non-null nodes, return False
1261. Find Elements in a Contaminated Binary Tree Medium Link Run BFS to change the value back, and use set() to find if a value exists

Binary Tree DFS

Binary Tree DFS
LeetCode 75
104. Maximum Depth of Binary Tree Easy Link
872. Leaf-Similar Trees Easy Link
1448. Count Good Nodes in Binary Tree Medium Link Standard DFS with slightly modification
437. Path Sum III Medium Link Use hashmap to keep track of current subtree's prefixSum, and update res with counts of diff = curSum - targetSum in current subtree's hashmap
1372. Longest ZigZag Path in a Binary Tree Medium Link Run DFS on each node, use goLeft to know if we should continue the path to node.left, we also run DFS on the opposite direction for each node with depth 1
236. Lowest Common Ancestor of a Binary Tree Medium Link Meta Tag Recursively go to root's left and right subtree to find if a node == p or node == q, if both node can be found, means the common ancestor is the root. Otherwise, either l or r is the ancestor
Miscellaneous
113. Path Sum II Medium Link Run DFS to reach the leaf and compare if curSum == targetSum, if so, copy the current path into res[], and pop, remove (backtrack) the current node.val to explore other paths
1650. Lowest Common Ancestor of a Binary Tree III Medium Link Meta Tag First save the path from p to root, traverse from q to root, the first common node is the LCA
543. Diameter of Binary Tree Easy Link Meta Tag Run DFS on each node to get its left, right subtree height and update res with left + right, for each node, return max(left, right) + 1
129. Sum Root to Leaf Numbers Medium Link Meta Run DFS to add every number in the path, when reaches the leaf node, return curSum, return node.left + node.right

Binary Search Tree

Binary Search Tree (BST) has property that the nodes on the left of the root are smaller than the root, the nodes on the right of the root are greater than the root. So, in many cases we can implement the DFS to perform In-order traversal: left -> root -> right.

Binary Search Tree
LeetCode 150
530. Minimum Absolute Difference in BST Easy Link Run DFS and set the left node as prev, then update res min(res, abs(prev.val-node.val)), change prev = node, go to its right
230. Kth Smallest Element in a BST Medium Link
98. Validate Binary Search Tree Medium Link
LeetCode 75
700. Search in a Binary Search Tree Easy Link
450. Delete Node in a BST Medium Link Run Binary Search to find the key, then replace the key with the second smallest element from its right branch deep left node to maintain the BST property
Miscellaneous
108. Convert Sorted Array to Binary Search Tree Easy Link
235. Lowest Common Ancestor of a Binary Search Tree Medium Link
938. Range Sum of BST Medium Link Meta Tag Based on the property of BST, we check if current node < low, we recursively call on its right subtree, if current node > high, we recursively call on its left subtree
426. Convert Binary Search Tree to Sorted Doubly Linked List Medium Link Meta Run DFS in-order traversal: left->root->right and update head.right = node and node.left = head, then update head = node. Finally, connect head and dummy together to be circular
270. Closest Binary Search Tree Value Easy Link Meta Compare the abs(node.val-target) with abs(res-target), if they equal, update res to be the smaller val, otherwise, update res to the one will smaller difference. Run DFS with Binary Search to find the closer one

Graph General

[286, 130, 417] require reverse-thinking to start running DFS on edges and add grids for some specific requirements. For other types of questions, we can run DFS or BFS iteratively to solve.

Graph General
200. Number of Islands Medium Link AutoX Tag Run BFS on each entry to find island that has not been visited
695. Max Area of Island Medium Link AutoX Tag
207. Course Schedule Medium Link DFS Run DFS to check all the prerequisites of a course, if can be completed, remove it and set preMap[crs] = []
210. Course Schedule II Medium Link
130. Surrounded Regions Medium Link
286. Walls and Gates Medium Link Graph BFS
417. Pacific Atlantic Water Flow Medium Link
133. Clone Graph Medium Link Meta Create each node's copy into hashmap{node: new_node}, run DFS to append each node's neighbors
399. Evaluate Division Medium Link
LeetCode 150
909. Snakes and Ladders Medium Link Graph BFS
127. Word Ladder Hard Link Graph BFS
433. Minimum Genetic Mutation Medium Link Graph BFS
LeetCode 75
841. Keys and Rooms Medium Link Graph DFS
547. Number of Provinces Medium Link Graph DFS For each unvisited city, run DFS to add all connected cities into visited(), increment res
1466. Reorder Routes to Make All Paths Lead to the City Zero Medium Link Graph DFS
994. Rotting Oranges Medium Link Graph BFS
1926. Nearest Exit from Entrance in Maze Medium Link Graph BFS
Miscellaneous
339. Nested List Weight Sum Medium Link Meta Tag Run DFS/BFS on each element in list, if this is element, update total with current depth and element's val. Otherwise, dfs on the list to update total with each element in that list with depth+1
1091. Shortest Path in Binary Matrix Medium Link Meta Run BFS to find the shortest path, add all the same level neighbors into visited and deque, update res += 1
827. Making A Large Island Medium Link Meta Run DFS/BFS start from an entry with 1 to change this island's every entry to be index. Traverse grid again to run BFS on 0 to calculate the area of its neighbors + 1
721. Accounts Merge Medium Link Meta Use hashmap to map {email: id} use uf.union() for existed email's id, then use uf.find() to find root_id and group {id: [email]}, lastly, follow the format to return
329. Longest Increasing Path in a Matrix Hard Link Meta 2D DP + DFS on entry's neighbors
1443. Minimum Time to Collect All Apples in a Tree Medium Link Meta Build adjacent graph and run DFS to search if node's children has apple, if so return secs + 2, otherwise, return 2 if node is apple, 0 else
489. Robot Room Cleaner Hard Link Run DFS and backtrack
2467. Most Profitable Path in a Tree Medium Link Run DFS to find path from bob to 0, then run BFS from 0 to all leaf nodes to find the maximum income for alice

Advanced Graph (Shortest Path)

Advanced Graph
743. Network Delay Time Medium Link Dijkstra's
787. Cheapest Flights Within K Stops Medium Link Bellman Ford
269. Alien Dictionary Hard Link Topological Sort/Post-order DFS
1976. Number of Ways to Arrive at Destination Medium Link Daily Question Run Dijkstra with list to record path and distance (time)

Union Find (Disjoint Set)

More to pratice:
547. Number of Provinces
952. Largest Component Size by Common Factor
947. Most Stones Removed with Same Row or Column
1319. Number of Operations to Make Network Connected
684. Redundant Connection
990. Satisfiability of Equality Equations
1202. Smallest String With Swaps
2421. Number of Good Paths

Union Find
721. Accounts Merge Medium Link Meta Use hashmap to map {email: id} use uf.union() for existed email's id, then use uf.find() to find root_id and group {id: [email]}, lastly, follow the format to return
2685. Count the Number of Complete Components Medium Link Daily Question Use union find or DFS to find connected components

Trie

Use {} to save this current node's next characters, "*" to indicate the end of a word.

Trie
208. Implement Trie (Prefix Tree) Medium Link
211. Design Add and Search Words Data Structure Medium Link
212. Word Search II Hard Link
1268. Search Suggestions System Medium Link

Intervals

Usually, we need to sort the array first to better find the overlapping intervals. We compare two intervals with the last element of previous interval and the first element of new interval to know detect overlap.

Intervals
56. Merge Intervals Medium Link Meta Compare new interval with previous interval, if there is overlap, we update the previous interval with [min(x1, x2), max(y1, y2)]. Otherwise, append the new interval to res[]
57. Insert Interval Medium Link
LeetCode 75
435. Non-overlapping Intervals Medium Link
452. Minimum Number of Arrows to Burst Balloons Medium Link Use prev to compare with current interval, if start <= prev[1], there is overlap and update prev
228. Summary Ranges Easy Link
1851. Minimum Interval to Include Each Query Hard Link
Miscellaneous
252. Meeting Rooms Easy Link First sort intervals, then use prev to save the previous interval's end time, then compare with new interval's start time, if prev > start, return False
253. Meeting Rooms II Medium Link Use minHeap to save all the current meeting with their end time. For each new interval, we compare their start_i with minHeap[0], if the start_i > minHeap[0], we replace the the room, otherwise, we append new end_i time into minHeap
986. Interval List Intersections Medium Link Meta Use two ptrs to find the intersection, keep the interval with greater end
636. Exclusive Time of Functions Medium Link Meta Use stack to store ids, identify start or end, and add the difference to res[i]
3169. Count Days Without Meetings Medium Link Daily Question Sort intervals, then count the gap between intervals
3394. Check if Grid can be Cut into Sections Medium Link Daily Question Sort intervals base on x, y coordiates. Then find if we can have at least 2 gaps for either x or y coordinate
836. Rectangle Overlap Easy Link AutoX Tag Check if rec1 is on the left, right, top, bottom of rec2, if none of them is true, that means they must overlap

Hashmap

In general, create a hashmap {} and store elements and their indices into the hashmap as the for-loop goes, then in the for loop we check if an element has already in the hashmap or not, or in the case we want to decrement the number of times we have seen an element in the hashmap.

Hashmap
1. Two Sum Easy Link
219. Contains Duplicate II Easy Link
242. Valid Anagram Easy Link
LeetCode 75
1207. Unique Number of Occurrences Easy Link Convert arr into hashmap, and add all occurences into set(), if an occurence already exisited in set(), return False. Otherwise, return True in the end
2215. Find the Difference of Two Arrays Easy Link Build two hashmaps and loop over to add non-repeatitive keys into set(), and convert to list and append to res
1657. Determine if Two Strings Are Close Medium Link Use two hashmaps and two sets() to compare if the strings' keys and values_counts are the same
2352. Equal Row and Column Pairs Medium Link Convert each row into str(row) and save into rows{}, then form str(col) and update res = rows[str(col)]
LeetCode 150
383. Ransom Note Easy Link
205. Isomorphic Strings Easy Link Build two hashmaps to compare the mapping of each two chars, if they don't match, return False
290. Word Pattern Easy Link Build a hashmap to check the previous mapping, but we also need to check if the mapping is unique, no duplicate words are used, we can use set() to compare
49. Group Anagrams Medium Link Sort word to be the key in hashmap, then append this word to the correpsonding list by the sorted(word) as key
202. Happy Number Easy Link Use set() to detect when there is repeated number, so we can stop
Miscellaneous
359. Logger Rate Limiter Easy Link Google VO
1726. Tuple with Same Product Medium Link Use dict with the multiplication of two integers as key, save two pairs of these two integers. Count each val number of permutation
2965. Find Missing and Repeated Values Easy Link Use set() to find the repeated value, later check elements from (1, n) not in set() as missing value
2206. Divide Array Into Equal Pairs Easy Link Daily Question Use hashmap to count each integer with their counts, then iterate hashmap to check if any counts % 2 != 0

Queue

Queue
933. Number of Recent Calls Easy Link Maintain a deque and pop the top when time expires
649. Dota2 Senate Medium Link Maintain 2 deques to fight with each party, the lower index party will win and requeue, the loser will not be added back. When one deque is empty, another party will announce victory
Miscellaneous
346. Moving Average from Data Stream Easy Link Meta Use deque[] to save k elements with curSum, when len(deque) == size, we remove the left-most element then add the right-most element into deque[]
239. Sliding Window Maximum Hard Link

Divide & Conquer

In most cases, we need to first find the mid point by len(nums) // 2, then recursively pass in mid point's left and right.
Divide & Conquer means we first divide the problem into several subproblems, we solve them and them merge teh results together.

Divide & Conquer
108. Convert Sorted Array to Binary Search Tree Easy Link
148. Sort List Medium Link
427. Construct Quad Tree Medium Link

Greedy

Greedy problems are hard to identify pattern, but one type of them can be solved by Kadane's Algorithm.

Greedy
53. Maximum Subarray Medium Link
55. Jump Game Medium Link
45. Jump Game II Medium Link
134. Gas Station Medium Link
846. Hand of Straights Medium Link
1296. Divide Array in Sets of K Consecutive Numbers Medium Link
763. Partition Labels Medium Link Maintain maxEnd for a letter's farthest index, if current index i == maxEnd, we find a partition
678. Valid Parenthesis String Medium Link
1899. Merge Triplets to Form Target Triplet Medium Link
Miscellaneous
670. Maximum Swap Medium Link Meta Use variables to keep track of the current maximum index and swap indices, update them based on num[i], finally check if both swap_ids are valid and swap, then return

Kadane's Algorithm

Kadane's Algorithm maintains a curSum which keep tracks of contiguous summation, it is always 0 if the curSum + nums[i] < 0, which means we will not take this element at index i. If curSum > 0 we will keep unpdating curSum += nums[i] and update maxSum = max(maxSum, curSum). This is the standard approach of Kadane's algorithm.

Kadane's Algorithm
LeetCode 150
53. Maximum Subarray Medium Link
918. Maximum Sum Circular Subarray Medium Link Use Kadane's alg to find globalMin and globalMax, return max(globalMax, sum(nums)-globalMin)
134. Gas Station Medium Link
Miscellaneous
1800. Maximum Ascending Subarray Sum Easy Link Kadane's Algorithm, when a non-ascending element exists, reset curSum = 0

1D DP

1D DP creates dictionary{} or list[] for cache, save time complexity to check repeated cases.

1D DP
LeetCode 75
1137. N-th Tribonacci Number Easy Link
746. Min Cost Climbing Stairs Easy Link
198. House Robber Medium Link
790. Domino and Tromino Tiling Medium Link
LeetCode 150
70. Climbing Stairs Easy Link
139. Word Break Medium Link Meta Build 1d DP to check if an index s[i:i+len(word)] == word, then we set dp[i] = dp[i+len(word)]
322. Coin Change Medium Link Build a dp table from range(0, amount+1), calculate how many coins need for each amount, take the current coin + dp(a-c)
300. Longest Increasing Subsequence Medium Link
123. Best Time to Buy and Sell Stock III Hard Link Save two dps of the maximum profit we can get at index i for its left maximum profit and right maximum profit
Miscellaneous
10. Regular Expression Matching Hard Link Amazon OA
2140. Solving Questions With Brainpower Medium Link Fill dp backward, and dp[i] should be the maximum points we can find in [i, n-1]

2D DP

Find pattern, base cases, then apply the recurrence relation to fill out the dp table. Sometimes, we can optimize 2D table to 1D array with a dp[] (row).

2D DP
62. Unique Paths Medium Link
72. Edit Distance Medium Link
1143. Longest Common Subsequence Medium Link
518. Coin Change II Medium Link
97. Interleaving String Medium Link
309. Best Time to Buy and Sell Stock with Cooldown Medium Link
714. Best Time to Buy and Sell Stock with Transaction Fee Medium Link
LeetCode 150
120. Triangle Medium Link
64. Minimum Path Sum Medium Link Build a dp table top-bottom, each entry takes its grid_val + min(dp_left, dp_up)
63. Unique Paths II Medium Link Modify the original grid as DP, each grid represents how many ways to go
188. Best Time to Buy and Sell Stock IV Hard Link Update profits of stock and cash for each transaction
221. Maximal Square Medium Link Find the minimum of three neighbors + 1 to update dp[r][c]
LeetCode 75
Miscellaneous
312. Burst Balloons Hard Link Backtrack + 2D DP
516. Longest Palindromic Subsequence Medium Link Build 2d DP with string s and its reverse, we compare if two chars are the same, if yes, we upate dp[r][c] = dp[r-1][c-1]+ 1, otherwise, we update dp[r][c] = max(dp[r-1][c], dp[r][c-1]
1216. Valid Palindrome III Hard Link Meta Build a dp table of s and s_reversed, check len(s) - dp[-1][-1] <= k so we know we can have k-palindrome
329. Longest Increasing Path in a Matrix Hard Link Meta 2D DP + DFS on entry's neighbors

Heap

Create a heap = [], then use heapq.heapify(nums) or just heapq.heappush(minHeap, i) to make a minHeap by default. If we want a maxHeap, we need to store the negative value heapq.heappush(maxHeap, -i), so the top will be the max value, when we pop the element, remember to negate it back.

$O(nlogn)$ for heapify(), $O(logn)$ for heappush() and heappop().

Heap
LeetCode 150
215. Kth Largest Element in an Array Medium Link Meta Tag Maintain a minHeap with k elements, the top of the minHeap is the kth largest element
502. IPO Hard Link Use two heaps
373. Find K Pairs with Smallest Sums Medium Link Save every elements of nums1 with the first index 0 of nums2 with the total sum
295. Find Median from Data Stream Hard Link Use two heaps
NeetCode 150
703. Kth Largest Element in a Stream Easy Link
1046. Last Stone Weight Easy Link
973. K Closest Points to Origin Medium Link Meta Tag Use minHeap to maintain k closest points
621. Task Scheduler Medium Link Use heap and deque
355. Design Twitter Medium Link
LeetCode 75
2336. Smallest Number in Infinite Set Medium Link Use a variable to keep track of the smallest when heap is empty
2542. Maximum Subsequence Score Medium Link Merged two nums together and sort them in descending order, maintain a heap with k elements for v1, update res by max(res, curSum * v2)
2462. Total Cost to Hire K Workers Medium Link Maintain 2 minHeaps for left and right, each of the minHeap has length candidates. Choose the lowest from these two minHeap, add new element to the minHeap
Miscellaneous
1094. Car Pooling Medium Link Daily Question Use minHeap to keep track of previous end position with number of passengers

Prefix Sum

Given an array arr[] of size N, find the prefix sum of the array. A prefix sum array is another array prefixSum[] of the same size, such that the value of prefixSum[i] is arr[0] + arr[1] + arr[2] . . . arr[i].

Prefix Sum
LeetCode 75
1732. Find the Highest Altitude Easy Link
724. Find Pivot Index Easy Link Maintain prefixSum and suffixSum, return i when they are equal
3028. Ant on the Boundary Easy Link Google Tag
560. Subarray Sum Equals K Medium Link Meta Use hashmap to save diff = curSum - k with its counts, if a diff = curSum - k in hashmap, we update res with diff's counts
Miscellaneous
437. Path Sum III Medium Link Use hashmap to keep track of current subtree's prefixSum, and update res with counts of diff = curSum - targetSum in current subtree's hashmap
Miscellaneous
528. Random Pick with Weight Medium Link Meta Tag First initialize each index from [0, len(w)-1] a probability by w[i] / sum(w), then we calculate the prefixSum of each index. Next, randomly generate a prob within [0, 1], then we use Binary Search to find the index with the closest probability

Bit Manipulation

For this type of question, we usually need to perform &, | (and, or) operation elementwise, and maybe need to shift bit by n >> 1 or n << 1 to move bits. Sometimes, we may need to start comparing two binary string backward, then return the reversed [::-1] version.

Bit Manipulation
LeetCode 150
67. Add Binary Easy Link
190. Reverse Bits Easy Link
191. Number of 1 Bits Easy Link
136. Single Number Easy Link XOR will eliminate the same element
137. Single Number II Medium Link Each bit's occurrences % 3 to update res's bit
201. Bitwise AND of Numbers Range Medium Link Right shift bits until left = right, also count how many bits we move, then move the bits left back
LeetCode 75
338. Counting Bits Easy Link Use dp to know how many 1s in the previous bits, and use i & 1 to know if the last bit is 1 or not
1318. Minimum Flips to Make a OR b Equal to c Medium Link Compare the last bits of a, b, c, and count how many flips we need
Miscellaneous
371. Sum of Two Integers Medium Link
2401. Longest Nice Subarray Medium Link Daily Question Maintain sliding window with a variable past by OR operation, if past has common bit with current digit, removing by XOR
3191. Minimum Operations to Make Binary Array Elements Equal to One I Medium Link Daily Question Loop over to check when nums[i] = 0, if the next two elements are in bound, we can flip them by XOR with 1

Math

Math
LeetCode 150
9. Palindrome Number Easy Link
66. Plus One Easy Link
69. Sqrt(x) Easy Link Run Binary Search in [0, x] to find the maximum m such that m^2 <= x
50. Pow(x, n) Medium Link Meta Tag Use a pattern to divide the exponent into half based on even or odd each time, so we can save the time complexity to be $O(log\ n)$
149. Max Points on a Line Hard Link For every point, save the slope of this point with other points as key, update with counts, udpate max everytime with current slope
172. Factorial Trailing Zeroes Medium Link Count number of 10 = 2 * 5, so we find the number of 5 that we can find
Miscellaneous
7. Reverse Integer Medium Link
1780. Check if Number is a Sum of Powers of Three Medium Link Iteratively minus $3^x$ from n if $3^x$ <= n
2579. Count Total Number of Colored Cells Medium Link Each time we update number of cells by multiple of 4
2790. Maximum Number of Groups With Increasing Length Hard Link Amazon Tag Sort it and find the pattern to satisfy each k group

Meta Tag

Meta Tag
1249. Minimum Remove to Make Valid Parentheses Medium Link Stack Use stack to save "(" index, when we encounter ")", we pop the last index from stack to close a parenthese. If we encounter ")" with no "(", change it to ""
227. Basic Calculator II Medium Link Stack Use stack to save previous result, we only append new element with sign into stack when we encounter a new sign
408. Valid Word Abbreviation Easy Link Array/String Use pointer for each string to compare, if abbr[j].isdigit(), we extract the number and increment i += int(number)
680. Valid Palindrome II Medium Link Two Pointers Use two ptrs to find where two chars are different, then check if s[l+1, r] or s[l, r-1] is a valid palindrome
314. Binary Tree Vertical Order Traversal Medium Link Binary Tree BFS Run BFS to save all the nodes with their column index [node, col] into deque and save them into hashmap {index: [node]}
215. Kth Largest Element in an Array Medium Link minHeap Maintain a minHeap with k elements, the top of the minHeap is the kth largest element
236. Lowest Common Ancestor of a Binary Tree Medium Link Binary Tree DFS Recursively go to root's left and right subtree to find if a node == p or node == q, if both node can be found, means the common ancestor is the root. Otherwise, either l or r is the ancestor
1650. Lowest Common Ancestor of a Binary Tree III Medium Link Binary Tree DFS First save the path from p to root, traverse from q to root, the first common node is the LCA
50. Pow(x, n) Medium Link Math Use a pattern to divide the exponent into half based on even or odd each time, so we can save the time complexity to be $O(log\ n)$
938. Range Sum of BST Medium Link Binary Search Tree Based on the property of BST, we check if current node < low, we recursively call on its right subtree, if current node > high, we recursively call on its left subtree
88. Merge Sorted Array Easy Link Array/String Compare nums1, nums2 backward and add the larger value into the end of nums1, use three pointers to keep track
339. Nested List Weight Sum Medium Link Graph General Run DFS/BFS on each element in list, if this is element, update total with current depth and element's val. Otherwise, dfs on the list to update total with each element in that list with depth+1
528. Random Pick with Weight Medium Link PrefixSum, Binary Search First initialize each index from [0, len(w)-1] a probability by w[i] / sum(w), then we calculate the prefixSum of each index. Next, randomly generate a prob within [0, 1], then we use Binary Search to find the index with the closest probability
162. Find Peak Element Medium Link Binary Search Run Binary Search to check if a peak element exists, if not, update l or r pointer to the greater value neighbor
199. Binary Tree Right Side View Medium Link Binary Tree BFS Run BFS on each level and only append the last node of each level to res[]
71. Simplify Path Medium Link Stack Detect each char to know if it equals to '/' or not, and use stack to add new file name or pop previous file name
125. Valid Palindrome Easy Link Two Pointers Use l, r ptrs to compare if two elem are the same, increment or decrement ptr if non-alphanumeric elem exists
543. Diameter of Binary Tree Easy Link Binary Tree DFS Run DFS on each node to get its left, right subtree height and update res with left + right, for each node, return max(left, right) + 1
560. Subarray Sum Equals K Medium Link prefixSum, hashmap Use hashmap to save diff = curSum - k with its counts, if a diff = curSum - k in hashmap, we update res with diff's counts
1. Two Sum Easy Link Hashmap/Array Save the remainder (target - nums[i]) into hashmap, when a remainder exists in hashmap, return [i, hashmap[nums[i]]]
973. K Closest Points to Origin Medium Link Heap Use minHeap to maintain k closest points
1570. Dot Product of Two Sparse Vectors Medium Link Array, Hashmap Use hashmap to save nonzero element with its index as key to hashmap{}. Update res with an index exists in both hashmaps
146. LRU Cache Medium Link Linked List, Hashmap, Deque Use two dummy nodes to keep track of the LRU and MRU, if we need to remove the LRU, remove right.prev. Insert to left.next to add new node. Access value by hashmap[key].val
791. Custom Sort String Medium Link Array, Hashmap Use hashmap to save each char in s with counts, traverse order and add char in hashmap with repeated times to res, traverse hashmap to add missing chars to res
1091. Shortest Path in Binary Matrix Medium Link Graph BFS Run BFS to find the shortest path, add all the same level neighbors into visited and deque, update res += 1
56. Merge Intervals Medium Link Intervals Compare new interval with previous interval, if there is overlap, we update the previous interval with [min(x1, x2), max(y1, y2)]. Otherwise, append the new interval to res[]
426. Convert Binary Search Tree to Sorted Doubly Linked List Medium Link Binary Search Tree, Linked List Run DFS in-order traversal: left->root->right and update head.right = node and node.left = head, then update head = node. Finally, connect head and dummy together to be circular
1762. Buildings With an Ocean View Medium Link Array Traverse heights from right to left, save the last height as curMax, if heights[i] > curMax, update curMax and save its index into res[], finally, return the reversed res[]
23. Merge k Sorted Lists Hard Link Linked List Merge 2 lists each time and replace lists with the merged sorted lists
863. All Nodes Distance K in Binary Tree Medium Link Binary Tree BFS Build an undirected graph to connect two connected nodes together, then run BFS from target to add all its neighbor nodes into deque, when distance == k, we append the node.val into res[]
921. Minimum Add to Make Parentheses Valid Medium Link String, Stack Count "(" and ")", when encounter ")", check if we have "(" to remove or decrement, otherwise, increment the count of ")"
346. Moving Average from Data Stream Easy Link Deque Use deque[] to save k elements with curSum, when len(deque) == size, we remove the left-most element then add the right-most element into deque[]
986. Interval List Intersections Medium Link Intervals Use two ptrs to find the intersection, keep the interval with greater end
138. Copy List with Random Pointer Medium Link Linked List Use hashmap to save each node with new node, traverse head to assign .next, .random to be the new node in hashmap
65. Valid Number Hard Link Array/String Keep track of seenDigit, seenExponent, seenDot, then we check if the current char is valid base on some rules
129. Sum Root to Leaf Numbers Medium Link Binary Tree DFS Run DFS to add every number in the path, when reaches the leaf node, return curSum, return node.left + node.right
1004. Max Consecutive Ones III Medium Link Sliding window Maintain sliding window with at most k 0, each time if nums[r] is 0, we decrement k, when k is negative, we update l += 1, same as moving the current max sliding window to the right
827. Making A Large Island Medium Link Graph General Run DFS/BFS start from an entry with 1 to change this island's every entry to be index. Traverse grid again to run BFS on 0 to calculate the area of its neighbors + 1
270. Closest Binary Search Tree Value Easy Link Binary Search Tree Compare the abs(node.val-target) with abs(res-target), if they equal, update res to be the smaller val, otherwise, update res to the one will smaller difference. Run DFS with Binary Search to find the closer one
76. Minimum Window Substring Hard Link Sliding Window Use two hashmaps and 2 counts to keep track of every chars, update res when sCount == tCount, and we start shrinking the sliding window
958. Check Completeness of a Binary Tree Medium Link Binary Tree BFS Run BFS with seenNull to check if a null node exists, if it exists and we have other non-null nodes, return False
415. Add Strings Easy Link Array/String Use two ptrs to access two chars backward + carry to perform addition, and append the result to []
2. Add Two Numbers Medium Link Linked List Create dummy node with carry to save the sum
1216. Valid Palindrome III Hard Link 2D DP Build a dp table of s and s_reversed, check len(s) - dp[-1][-1] <= k so we know we can have k-palindrome
31. Next Permutation Medium Link Array Find index such that nums[i] < nums[i+1], then find another element nums[j] > nums[i] from backward, swap them, and reverse nums[i+1:]
78. Subsets Medium Link Backtrack Use backtrack with index i to keep track of current curSum[], when i==len(nums), we append curSum into res[] and return, we pop the last element and add new element into curSum with i += 1
133. Clone Graph Medium Link Graph General Create each node's copy into hashmap{node: new_node}, run DFS to append each node's neighbors
987. Vertical Order Traversal of a Binary Tree Hard Link Binary Tree General Save (node, row, col) into deque[], and run BFS to append node.left with (row+1, col-1) and node.right with (row+1, col+1). Add all nodes with the same col into hashmap{col: [node.val]}. Sort col and row in the end
670. Maximum Swap Medium Link Greedy Use variables to keep track of the current maximum index and swap indices, update them based on num[i], finally check if both swap_ids are valid and swap, then return
721. Accounts Merge Medium Link Union Find, DFS Use hashmap to map {email: id} use uf.union() for existed email's id, then use uf.find() to find root_id and group {id: [email]}, lastly, follow the format to return
1539. Kth Missing Positive Number Easy Link Binary Search Run Binary Search with k on the difference between the original arr and current arr
139. Word Break Medium Link 1D DP Build 1d DP to check if an index s[i:i+len(word)] == word, then we set dp[i] = dp[i+len(word)]
708. Insert into a Sorted Circular Linked List Medium Link Linked List Use prev, curr to keep track of two nodes and compare their values with insertVal and add new Node between prev and curr
34. Find First and Last Position of Element in Sorted Array Medium Link Binary Search Find the left end and right end of nums by running Binary Search twice, update different ptr each time
1768. Merge Strings Alternately Easy Link Two Pointers Use two ptrs to add chars from two strings alternatively, then check to add the remaining from word1 or word2
498. Diagonal Traverse Medium Link Matrix Save the diagonal index by (r+c) with values {diagonal_idx: [val]}, then check idx % 2 to decide whether reverse the saved values' list or not
605. Can Place Flowers Easy Link Array Append 0 to two ends of flowerbed, check flowerbed[i] and its neighbors are all 0 or not, if so, replace 0 to 1 and decrement n. Return n <= 0
329. Longest Increasing Path in a Matrix Hard Link 2D DP, Graph General 2D DP + DFS on entry's neighbors
766. Toeplitz Matrix Easy Link Matrix Compare each entry with their bottom-right neighbor (if exists)
1443. Minimum Time to Collect All Apples in a Tree Medium Link Graph General, DFS Build adjacent graph and run DFS to search if node's children has apple, if so return secs + 2, otherwise, return 2 if node is apple, 0 else
224. Basic Calculator Hard Link Stack Use res, sign ,curr to keep track of previous operation result, update res when we have new sign, append res, sign into stack[] when we have "(". Calculate result within (), and pop everything back from stack[], reset variables
一亩三分地
347. Top K Frequent Elements Medium Link minHeap Count num with their counts, use minHeap to sort the counts then append num k times from minHeap to res[]
71. Simplify Path Medium Link Stack Detect each char to know if it equals to '/' or not, and use stack to add new file name or pop previous file name
698. Partition to K Equal Sum Subsets Medium Link Array, Backtrack Use Backtrack to try each element with other elements subarray, if the subarray equals to k, we mark all elements to be visited, run backtrack from the beginning again. For every subarray, we decrement k -= 1, return True when k == 0
36. Valid Sudoku Medium Link Matrix Use three dicts to check repetition
37. Sudoku Solver Medium Link Matrix, Backtrack Use 3 sets to save existed vals, backtrack number i from [1, 9] for '.'
636. Exclusive Time of Functions Medium Link Meta Use stack to store ids, identify start or end, and add the difference to res[i]

Amazon Tag

Amazon Tag
146.LRU Cache Medium
767.Reorganize String Medium
2790. Maximum Number of Groups With Increasing Length Hard Link Sort it and find the pattern to satisfy each k group

Concurrency

Concurrency
1114. Print in Order Easy Link Semophores to lock resource and wait to release
1116. Print Zero Even Odd Medium Link From zero() we identify and unlock the semophores for even() or odd() base on the i, then we printNumber(i) and unlock sem_zero to back continue
1115. Print FooBar Alternately Medium Link Set sem_foo with higher priority, so we can always start with foo, then release sem_bar
1117. Building H2O Medium Link Use two semaphores for hydrogen and oxygen, allow 2 hydrogen can be accessed at the same time, use count to unlock sem_oxy
1188. Design Bounded Blocking Queue Medium Link Using two semaphores with one mutex, define one semaphore with capacity

SQL

SQL
1757. Recyclable and Low Fat Products Easy Link
584. Find Customer Referee Easy Link
595. Big Countries Easy Link
1378. Replace Employee ID With The Unique Identifier Easy Link



CC BY-NC-SABY: credit must be given to the creatorNC: Only noncommercial uses of the work are permittedSA: Adaptations must be shared under the same terms