- Array / String
- Two Pointers
- Sliding Window
- Matrix
- Binary Search
- Backtracking
- Stack
- Monotonic Stack
- Linked List
- Binary Tree General
- Binary Tree BFS
- Binary Tree DFS
- Binary Search Tree
- Graph General
- Advanced Graph (Shortest Path)
- Trie
- Intervals
- Hashmap
- Queue
- Divide & Conquer
- Greedy
- Kadane's Algorithm
- 1D DP
- 2D DP
- Heap
- Prefix Sum
- 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.
| Array / String | ||||
|---|---|---|---|---|
| LeetCode 150 | ||||
| 88. Merge Sorted Array | Easy | Link | 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 | ||
| 122. Best Time to Buy and Sell Stock II | Medium | Link | ||
| 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 | |
| 347. Top K Frequent Elements | Medium | Link | Amazon | |
| 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 | ||
| 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 | ||
| 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 |
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 | ||||
|---|---|---|---|---|
| LeetCode 150 | ||||
| 125. Valid Palindrome | Easy | Link | 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 |
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 | ||
| 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 | ||
| 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 |
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 | Link | |
| 54. Spiral Matrix | Medium | Link | ||
| 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 |
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 | ||||
|---|---|---|---|---|
| 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 | 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 | ||
| 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 |
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 | 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 | ||
| 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 |
| 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 | |
| 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 |
| Miscellaneous | |||
| 224. Basic Calculator | Hard | Link | Google VO |
| 84. Largest Rectangle in Histogram | Hard | Link | Google Tag |
| Monotonic Stack | |||
|---|---|---|---|
| 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 | |||
|---|---|---|---|
| 141. Linked List Cycle | Easy | Link | |
| 21. Merge Two Sorted Lists | Easy | Link | |
| 2. Add Two Numbers | Medium | 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++ |
| 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 |
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 | |
| 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 |
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 | Standard Tree BFS |
| 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 |
| 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 | |
| 236. Lowest Common Ancestor of a Binary Tree | Medium | Link | 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 |
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 |
[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 | Graph BFS | Run BFS on each entry to find island that has not been visited |
| 695. Max Area of Island | Medium | Link | Python, Java | |
| 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 | ||
| 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 |
| 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 |
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 |
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 | ||
| 242. Valid Anagram | Easy | Link | ||
| LeetCode 75 Hashmap/Set | ||||
| 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 | |
| Miscellaneous | ||||
| 359. Logger Rate Limiter | Easy | Link | Google VO |
| 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 |
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 | ||||
|---|---|---|---|---|
| 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 | ||
| 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 | ||
| Miscellaneous | ||||
| 10. Regular Expression Matching | Hard | Link | Amazon OA |
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 | |
| LeetCode 150 | |||
| 120. Triangle | Medium | Link | |
| LeetCode 75 | |||
| Miscellaneous | |||
| 312. Burst Balloons | Hard | Link | Backtrack + 2D DP |
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.
| Heap | ||||
|---|---|---|---|---|
| LeetCode 150 | ||||
| 215. Kth Largest Element in an Array | Medium | Link | Maintain a minHeap with k elements | |
| 502. IPO | Hard | Link | Use two heaps | |
| 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 | ||
| 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 |
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 | Maintain hashmap to keep track of prefix with their counts, if a diff = curSum - k in hashmap, we update res with the 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 |
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 | XOR will eliminate the same element | |
| 191. Number of 1 Bits | Easy | Link | ||
| 190. Reverse Bits | Easy | Link | ||
| 67. Add Binary | Easy | Link | ||
| 371. Sum of Two Integers | Medium | Link | ||
| 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 |
| 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 |
