- Array / String
- Two Pointers
- Sliding Window
- Matrix
- Binary Search
- Backtracking
- Stack
- Linked List
- Binary Tree General
- Binary Tree BFS
- Binary Search Tree
- Graph General
- Advanced Graph (Shortest Path)
- Trie
- Intervals
- Hashmap
- Divide & Conquer
- Greedy
- Kadane's Algorithm
- 1D DP
- 2D DP
- Heap
- Bit Manupulation
- Math
- Others
General cases we want to replace element with non-repeating element in nums, so we set an index to keep track of repeating position.
Two pointers can save space complexity, because it only uses constant space complexity l, r pointers and either increment l or decrement r depends on the current sum compare with target value.
| Two Pointers | ||||
|---|---|---|---|---|
| 125. Valid Palindrome | Easy | Link | ||
| 167. Two Sum II - Input Array Is Sorted | Medium | Link | ||
| 392. Is Subsequence | Easy | Link | ||
| 11. Container With Most Water | Medium | Link | ||
| 15. 3Sum | Medium | Link | ||
| 1268. Search Suggestions System | Medium | Link | ||
| 5. Longest Palindromic Substring | Medium | Link | Python | Amazon, Cisco |
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 | ||
|---|---|---|
| 3. Longest Substring Without Repeating Characters | Medium | Link |
| 121. Best Time to Buy and Sell Stock | Easy | Link |
| 53. Maximum Subarray | Medium | Link |
| 209. Minimum Size Subarray Sum | Medium | Link |
| 424. Longest Repeating Character Replacement | Medium | Link |
| 76. Minimum Window Substring | Hard | Link |
| 239. Sliding Window Maximum | Hard | Link |
| 567. Permutation in String | Medium | Link |
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 |
| 54. Spiral Matrix | Medium | Link |
| 48. Rotate Image | Medium | Link |
| 73. Set Matrix Zeroes | Medium | Link |
This is the approach when we are required to write an algorithm with (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 | ||
|---|---|---|
| 704. Binary Search | Easy | Link |
| 35. Search Insert Position | Easy | Link |
| 74. Search a 2D Matrix | Medium | Link |
| 875. Koko Eating Bananas | 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 |
| 34. Find First and Last Position of Element in Sorted Array | Medium | Link |
| 4. Median of Two Sorted Arrays | Hard | Link |
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 |
| 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 |
| 77. Combinations | Medium | Link |
| 22. Generate Parentheses | Medium | Link |
| 46. Permutations | Medium | Link |
| 79. Word Search | Medium | Link |
| 131. Palindrome Partitioning | Medium | Link |
| 51. N-Queens | Hard | Link |
| 52. N-Queens II | Hard | Link |
| Stack | ||
|---|---|---|
| 20. Valid Parentheses | Easy | Link |
| 155. Min Stack | Medium | Link |
| 150. Evaluate Reverse Polish Notation | Medium | Link |
| 22. Generate Parentheses | Medium | Link |
| 739. Daily Temperatures | Medium | Link |
| Linked List | |||
|---|---|---|---|
| Problems | Difficulty | Link | Languages |
| 141. Linked List Cycle | Easy | Link | |
| 21. Merge Two Sorted Lists | Easy | Link | |
| 2. Add Two Numbers | Medium | Link | |
| 206. Reverse Linked List | Easy | Link | |
| 92. Reverse Linked List II | Medium | Link | |
| 138. Copy List with Random Pointer | Medium | Link | |
| 143. Reorder List | Medium | Link | |
| 19. Remove Nth Node From End of List | Medium | Link | |
| 146. LRU Cache | Medium | Link | |
| 25. Reverse Nodes in k-Group | Hard | Link | Python |
| 61. Rotate List | Medium | Link | Python, C++ |
| 23. Merge k Sorted Lists | Hard | Link | Python, C++ |
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 | ||
|---|---|---|
| 104. Maximum Depth of Binary Tree | Easy | Link |
| 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 |
| 222. Count Complete Tree Nodes | Easy | Link |
| 112. Path Sum | Easy | Link |
| 236. Lowest Common Ancestor of a Binary Tree | Medium | Link |
| 124. Binary Tree Maximum Path Sum | Hard | Link |
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 |
| 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 |
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 | ||
|---|---|---|
| 530. Minimum Absolute Difference in BST | Easy | Link |
| 230. Kth Smallest Element in a BST | Medium | Link |
| 98. Validate Binary Search Tree | Medium | Link |
| 108. Convert Sorted Array to Binary Search Tree | Easy | Link |
| 235. Lowest Common Ancestor of a Binary Search Tree | Medium | Link |
| 700. Search in a Binary Search Tree | Easy | Link |
| 450. Delete Node in a BST | Medium | Link |
[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 | Python, C++ |
| 695. Max Area of Island | Medium | Link | Python, Java |
| 207. Course Schedule | Medium | Link | Python |
| 210. Course Schedule II | Medium | Link | Python |
| 130. Surrounded Regions | Medium | Link | Python |
| 286. Walls and Gates | Medium | Link | Graph BFS |
| 417. Pacific Atlantic Water Flow | Medium | Link | Python |
| 133. Clone Graph | Medium | Link | Python |
| 399. Evaluate Division | Medium | Link | Python |
| 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 |
| 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 |
| 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 |
| 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 |
Usually, we need to sort the array first to better find the overlapping intervals. We compare two intervals with the last element of the interval and the first element of another interval to know whether they are overlapped or not.
| Intervals | ||
|---|---|---|
| 56. Merge Intervals | Medium | Link |
| 57. Insert Interval | Medium | Link |
| 435. Non-overlapping Intervals | Medium | Link |
| 228. Summary Ranges | Easy | Link |
| 452. Minimum Number of Arrows to Burst Balloons | Medium | Link |
| 1851. Minimum Interval to Include Each Query | Hard | Link |
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 |
| 383. Ransom Note | Easy | Link |
| 242. Valid Anagram | Easy | Link |
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 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 |
| 678. Valid Parenthesis String | Medium | Link |
| 1899. Merge Triplets to Form Target Triplet | Medium | Link |
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 | ||
|---|---|---|
| 53. Maximum Subarray | Medium | Link |
| 134. Gas Station | Medium | Link |
1D DP creates dictionary{} or list[] for cache, save time complexity to check repeated cases.
| 1D DP | ||
|---|---|---|
| 70. Climbing Stairs | Easy | Link |
| 746. Min Cost Climbing Stairs | Easy | Link |
| 1137. N-th Tribonacci Number | Easy | Link |
| 198. House Robber | Medium | Link |
| 139. Word Break | Medium | Link |
| 300. Longest Increasing Subsequence | Medium | Link |
| 322. Coin Change | Medium | Link |
| 10. Regular Expression Matching | Hard | Link |
| 790. Domino and Tromino Tiling | Medium | Link |
In 2D DP, we usually need to create a dP table, then we start filling out the entries by bottom-up method taking sum or choosing the minimum entry from right, below, or diagonal. But before that, we need to find a pattern first, then apply pattern to the dP table. Usually, we can reduce from storing the whole 2d table into only storing the previous row/col.
| 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 |
Usually we need to use create a heap = [], then use heapq.heapify or just heapq.heappush to make that heap becomes 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.
| Heap | ||||
|---|---|---|---|---|
| 703. Kth Largest Element in a Stream | Easy | Link | ||
| 215. Kth Largest Element in an Array | Medium | Link | ||
| 1046. Last Stone Weight | Easy | Link | Python, Java, C++ | |
| 973. K Closest Points to Origin | Medium | Link | Python | |
| 295. Find Median from Data Stream | Hard | Link | Use two heaps | |
| 502. IPO | Hard | Link | Python | Use two heaps |
| 621. Task Scheduler | Medium | Link | Python | Use heap and deque |
| 355. Design Twitter | Medium | Link |
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 | ||
|---|---|---|
| 136. Single Number | Easy | Link |
| 191. Number of 1 Bits | Easy | Link |
| 190. Reverse Bits | Easy | Link |
| 67. Add Binary | Easy | Link |
| 371. Sum of Two Integers | Medium | Link |
| Math | ||
|---|---|---|
| 9. Palindrome Number | Easy | Link |
| 66. Plus One | Easy | Link |
| 7. Reverse Integer | Medium | Link |
| Others | ||
|---|---|---|
| 239. Sliding Window Maximum | Hard | Link |
| 287. Find the Duplicate Number | Medium | Link |
