Easy
| Problem | Type | Key Ideas |
|---|---|---|
| Climbing Stairs | Dynamic Programming | Base cases: 0 and 1 step is 1 way Brute force cur = helper(n - 1) + helper(n - 2) with memoisation |
| Maximum Unique Subarray Sum After Deletion | Array | Use if all(n < 0 for n in nums): return max(nums) to handle the case where all the elements are negativeLoop through the entire array otherwise and sum all the non negative numbers while keeping track of numbers that have been added before |
| Binary Tree Preorder Traversal | Tree | Naive approach - Recursion: Adding current value and then recursing on the left and right subtrees Iterative approach with O(n) space: Use a stack to emulate the recursive call stack, adding the current values and pushing the right subtree to the stack if it exists, and repeating on the left subtree Morris traversal with O(1) space: While root is not null: 1 - If left subtree is null, root = root.right 2 - Otherwise find the predecessor of the root (right most node in the left subtree) and check if its right child is already set to root ⇒ left subtree has been visited, move root to right subtree now 3 - Otherwise set the predecessor’s right child to be the root and move root to the right Key idea is that once we find that the predecessor’s right child is already set to the root, means we have come to the case of revisiting the root, so we just revert the right and move on to the right subtree |
| Maximum Value of an Ordered Triplet I | Array | O(n^3) TC: Brute force triple for loop O(n^2) TC: Take the max of i while iterating, and use 2 for loops to find j and k O(n) TC and SC: Create suffix sum for k (and prefix for i but not necessary) to find the max value of k at each index, and use technique of maintain max i in second solution to do a one pass solution O(n) TC and O(1) SC: Maintain max_i and max i -j while fixing k, and iterate through with a one pass for each value of k, while updating the max_i and max i- j for each iteration |
| Power of Two | Binary, Math | O(1) TC with loops: Since the max value of n is 2^32, we just have to have a while loop of x^2 for a max of 32 times, and check if x == n at the end Binary solution: All powers of 2 are in the form of 0001, 0010, 0100, 1000 etc We can take the inverse of the binary of n using n - 1, only works if the binary has only one 1 in it |
Medium
| Problem | Type | Key Ideas |
|---|---|---|
| LRU Cache | Design | Hashmap for O(1) cache access, with key as the actual key and value being the node in the double ended linked list, Node(key, value) Double ended linked list to store the least and most recently used node for O(1) get and put, using helper functions to reorder when node is used. Use a dummy node to point to the start and end. |
| Coin Change | Dynamic Programming | Bottom up DP, base case where we want to sum to 0 is 0 coins Initialise a DP array to store the number of coins needed for all cases to be infinity Followed by calculating the number of coins needed to sum from 0 to target amount using memoisation and brute force recursion |
| Jump Game | Dynamic Programming | Brute force solution: Without memoisation, time complexity is roughly n^n Greedy solution: start with the final index (goal) and check if there is any preceding index that can reach it. If possible, then the new goal will be the index that can reach it for subsequent indices. If we reach the start of the array where the we can reach the goal then it is possible, otherwise impossible TC: O(n) Dynamic Programming: Use recursion to check every possible step from the first index and subsequent indices, and if the recursive call reaches the end, memoise the result to true, otherwise memoise the result to false TC: O(n^2), SC: O(n) |
| Number of Connected Components in a Undirected Graph | Graph | Union find disjoint set to union 2 nodes if they have an edge connecting them, using a helper function to find the parent of the node Initialise a parent and rank array, where parent tracks the node’s parent by index (if the node is a parent of itself, then it is the root node), and the rank array to store the weight of the node (for tree balancing) Find operation to find the parent of the node, using path compression as we iterate through the node’s parent Union operation to combine 2 nodes into a tree using the find operation, and ensure balancing of the trees using weights For each successful union operation, subtract 1 from the number of nodes, and the result is the answer of how many disjoint sets Alternatively, use DFS |
| Combination Sum | Backtracking | Backtracking and creating a copy of the array to add to result Recursion tree can either use the current ith value for subsequent recursive calls, or move on to the next value in the candidates |
| Combination Sum II | Backtracking | Similar approach to version 1, but we sort to group duplicates together, and use the two branch approach to remove duplicates: either to take the element or not. O(n * 2^n) time complexity: 2^n because for each element, we either take or don’t take it, and for each array, we have to make a copy and add it to the result array O(n) space: Size of the recursive call stack or the accumulated array if we do not count the result array |
| Longest Palindromic Substring | String | O(n^3) Solution: For every substring (O(n^2) substrings), check if it is a palindrome by using 2 pointers, either starting from the centre until the middle, or middle and expand outwards (O(n) time) O(n^2) Solution: Instead of checking for all substrings, we can iterate through the string and check for substrings using the current character as the center of the palindrome. Doing this will iterate through O(n) length of the string, and each check will take O(n) time |
| Pow(x, n) | Math | O(n) Solution: While loop or recursion where the result is multiplied by x until n is 0 O(log n) Solution: Divide and conquer approach, eliminate repeated work by computing only half the power and taking the power of 2 of the result, and taking the reciprocal if needed |
| House Robber | Dynamic Programming | O(n) time complexity with O(n) space solution: Recurrence relation: dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) Idea: Initialise base cases for nums array length of 1 and 2, then use the recurrence relation to solve O(n) time complexity with O(1) space solution: We actually do not need to initialise a dp array, since we do not need to access the elements that are more than 2 positions behind the current element, so we could just use 2 variables and swap them with a temp variable |
| House Robber II | Dynamic Programming | O(2n) solution Similar to House Robber, but arranged in a circle, so we need to consider whether we are robbing the first house or not, reusing the solution from house robber Using the same solution from House Robber 1 as a function, we run it twice without the first house and without the last house and find the max between both calls Edge case: if the house array is length 1, the function will return 0, so we need to consider the first house for the case with array of size 1 |
| Decode Ways | String | O(2^n) solution is to look at every decision down the decision tree, whether to take the current index or take it with the next. Each character has 2 choices, so 2^n O(n) space and time complexity solution with caching: Subproblem is how many ways we can decode the string at the [i + 1] index, if the numbers are valid O(n) time complexity without extra memory: Recurrence relation: dp[i] = dp[i + 1] + dp[i + 2] Similar to the house robber problem, we do not need an entire array to store the result, but just 2 variables |
| Unique Paths | Dynamic Programming | Memoisation DP Approach with O(mn) TC and SC: Brute force going through all grids and memoise the result once it has been computed. Initial mistake is to count the number of total steps to get to the end, but we should be returning 1 only when we reach the end and memoise the solution Bottom up DP approach with O(mn) TC and O(n) SC: Note that the number of unique paths to get from any grid in the last row or last column is 1, so we can fill that up. Then, the recurrence relation is dp[x, y] = dp[x + 1, y] + dp[x, y + 1] so we can compute it row by row without having to initialise a dp table of m*n |
| Word Break | String, Dynamic Programming | Brute force solution 1 with O(n^2): Check every substring and see if the word exists in the wordDict, if yes, recurse on the other part of the word without the current word Brute force solution 2 with O(m * n^2): For every word in the wordDict, check if the front of the string has the word. Potentially go through every starting position so O(n), and comparing with O(m) words in the word dictionary which takes O(n) time Brute force solution 2 with caching: cache the ith position if we cannot find a word from that index Bottom up DP approach: Start from the back of the string and check if we can find a word in the wordDict at the ith index, and store the boolean in a DP array for each ith equation Recurrence relation: dp[i] = dp[i + len(word)] Return dp[0] Potential bugs: remember to break once we have set dp[i] to be true to prevent overriding a true, also only check the required word, not if the word exists in the current substring |
| Zigzag Conversion | String | O(n) solution: Elements on the top and bottom row are 2 * (numRows - 1) hops away from each other, and there are also additional elements in between those 2 indices for the middle rows which are 2 * (numRows - 1) - 2r hops away from the current index. Use array to avoid O(n) operation of concatenating strings. Brute force solution: Initialise a 2D array to hold the positions of the characters, and loop through each character and place it in the correct spot, checking if it needs to be going down or diagonally up |
| Permutations | Backtracking | TC: O(n! * n^2), SC: O(n! * n): Break the array into a subproblem, recursively call the the function on the subarray without the first element, then try to insert the element in all the possible positions Iterative approach: for every number in nums, try to insert the number into all possible positions in each array in perms Important to create a copy of the array before adding elements |
| Permutations II | Backtracking | Convert the array of nums into a hashmap to store the number of times each number appears. This eliminates moving on with duplicates in the next layer of the decision tree, because we either do not have repeated elements at the same layer. Code: convert nums into a counter hashmap and recursively add every available n into the permutation and go deeper, then backtrack by adding the count of the element back and remove from the permutation array TC is probably O(n * 2^n) or O(n * n!) because for each permutation we have to copy it (O(n)) and there is either n! or 2^n steps |
| 4Sum | Arrays, Two Pointers | Naïve approach: Have 2 for loops to select each variable, and for the rest of the variables, we use 2 pointers to find the target, having sorted them first General approach: Use recursion to track the number of numbers left we have to select, and the base case 2 will use the left and right pointer approach to find the target, allowing us to do k sum def kSum(k, start, target) |
| Letter Combinations of a Phone Number | Backtracking | Create mapping of integers to letters, define helper function to add all possible letters for each number and accumulate all possible permutations Need base case for empty digits string Note that key for map has to be a string, since the digits are characters in a string |
| Maximum Score From Removing Substrings | String | Data structure: Stack Two phase approach, remove all the occurrences of substring with the higher score first, followed by the other Why does this work? A few scenarios assuming ab is larger: xaby: removing ab will not introduce a new pair because any non ab characters is a ‘wall’ aaba, babb: will not create new pairs aabb, baba: create new pairs, with baba, if we remove ab, the new pair ba will be cleared in the second phase For the second case: abaa, bbab: no new pairs abab: not possible to happen, abab will be removed in the first phase bbaa: second phase will handle the second ba that forms Code: Use nonlocal s to modify s in the helper function, use a stack to track the characters seen and pop if it is the dominant string, and join the stack to set to s. Set variable pair to be ‘ab’ if x > y otherise ‘ba’, and reverse it for the second helper function call |
| Valid Sudoku | Array | O(n^2) time and space complexity: Initialise a collections.defaultdict(set) for rows, cols and grids. Iterate through every element in the board, checking if the element already exists in its row, col and grid. Grid is calculated by taking floor division of the row and col of the current element, and the key that is stored in the grid hash table is (r // 3, c // 3) |
| Jump Game II | Dynamic Programming | O(n) time complexity, BFS style: Maintain a left and right pointer to track which level we are on in the array, and for every iteration, find the next level of BFS until we reach the end of the array. The number of BFS levels is the number of jumps |
| Unique Paths II | Dynamic Programming | Brute force + Memoisation TC:O(n^2) DP Approach: TC O(MN), SC O(n): Can use only a row of memory as we do not need to store the same value twice after we have computed it. Same as unique paths i, but take obstacle into consideration where we set the dp array element to be 0 if we encounter an obstacle, otherwise dp[c] = dp[c] + dp[c + 1] |
| Longest Consecutive Sequence | Array | O(n) time and space complexity: convert the nums array into a set and iterate through the elements in the array, if n - 1 not in the set, then we can check what is the longest sequence using n + length |
| Fruit Into Baskets | Sliding Window | O(n) TC and SC: Expand the window while keeping track of count of the number of elements in the window. If it exceeds 2 items, then shift the left pointer until the number of items fall back to 2. Use a defaultdict to initialise 0 values, and use dict.pop(item) to remove the key from the dictionary when the count is 0 |
| Daily Temperatures | Stack | O(n) TC and SC with monotonic decreasing stack: Use a stack to track what temperatures we have not found a greater temperature for, and once found, we can pop the stack and label the number of days it took |
| Fruits Into Baskets III | Segment Tree | O(nlogn) TC and O(n) SC: Build a segment tree which maintains the max of size of the baskets on the left and right subtree |
| Car Pooling | Array | O(nlogn) TC: Similar to meeting rooms, but use a minHeap to track the trips that have yet to be completed, as well as the current capacity. Sort the trips by starting index and iterate through it, add the number of passengers and checking if there are trips that have been completed using the min heap, and subtracting number of passengers if it has finished. O(n) TC hack: Since the constraints are the start and end indices are between 0 and 1000, we can just create an array of size 1001 which states the change of passengers at each index. Then, loop through the array and calculate the number of passengers at each index, checking if the capacity has exceeded, O(1000) TC |
| Smallest Missing Non-negative Integer After Operations | Array, MEX | O(n) TC and SC:Use a hashmap to count the number of available numbers that have number % value, as we can add or subtract value from the number any amount of times. Then use a for loop to check every index from 0 to len(nums) - 1 whether there is a available number to add/remove value to get to that index, if not that is the minimum number |
| Max Number of K-Sum Pairs | Array | O(nlogn) TC and O(1) SC: Two sum solution, but don’t terminate after finding O(n) TC and O(n) SC: Similar to two sum hashmap solution, check if the complementary is in the hashmap, and subtract the count if it is, otherwise add the current number into the hashmap count |
| Reverse Words in a String | String | O(n) TC: Hack: use s.split() to arrays of only words, then use two pointers to swap words from the front and back of the array Otherwise iterate through the string and use two pointers to find words to add to an array, then join |
| Minimum Number of Arrows to Burst Balloons | Greedy | O(n) TC: Sort the array by starting point, and greedily expand the end point until a balloon does not have a start point before the accumulated end point and increment |
| Increasing Triplet Subsequence | Array | O(n) TC: Track the first and second most minimum numbers while iterating through the array, and check if the condition holds |
| Reordered Power of 2 | Array | O(d * d!) TC and SC solution: Where d = len(n), we create all permutations of the number n and check if each permutation is a power of two. math.log(n, 2) is not accurate, so we need to use num & (num - 1) == 0 to check if the number is a power of 2 O(1) TC and O(d) TC: create a frequency counter of each digit, and check if it is equal to any frequency count of power of 2 up to 2 ^ 29. Note: 1 << i == 2 ** i |
| Range Product Queries of Powers | Binary | To find the minimum number of powers of 2 to add to n, we have to take the binary representation of n, and for each k-th binary digit, if it is 1, then the power of 2 is included. Then compute the prefix sum of the powers, and calculate the query |
| New 21 Game | Dynamic Programming, Sliding Window | O(k * maxPts) TC: Brute force + memoisation using a helper function, iterating through the possible values that we can get from some points value and calculating the probability of having points that are less than n and more than k at each value O(k + maxPts) TC and O(k) SC: Instead of calculating the probability of attaining a point ⇐ n and > k, we can have a accumulative sum for a sliding window problem, initialising the values from k to k + maxPts as the base case, 1 if it is ⇐ n otherwise 0. Then calculate the probability for each position from k - 1 to 0, and updating the probability and sliding window each time |
| Design a Food Rating System | Design | init: Create a cuisineToRating hashmap to map cuisine to (rating, food) to have O(logn) of highestRated. Also create a foodToCuisine hashmap to find what cuisine the food belongs to for changeRating, as well as foodToRating hashmap, so that we can do lazy deletion of items in the heap changeRating: Use the foodToCuisine hashmap to find the cuisine of the food, and push (-1 * newRating, food) into the respective hashmap highestRated: Repeated find the top of the heap until we find a rating that matches our hashmap foodToRating, since the heap can contains stale values, and pop the stale values out as well |
| Minimum Score Triangulation of Polygon | Dynamic Programming | O(n^3) TC: n^2 inputs and each input does n, so n^3 O(n^2) SC: cache stores all n^2 inputs Idea is to form triangles using the edge left → right, and find another point in the polygon that is a potential triangle with it. Each time we do this, the polygon splits into 2 smaller polygons, and we can repeat this step until the polygon becomes a triangle and we can compute the weight of the triangle. IE we find every possible triangle we can form using left, right and some other point, and the recurrence relation is: best = min(best, values[left] * values[right] * values[mid] + f(left, mid) + f(mid, right)) |
Hard
| Problem | Type | Key Ideas |
|---|---|---|
| Alien Dictionary | Graph | Topological sort on a DAG, followed by Post order DFS with loop detection Build adjacency list for each character, then do post order DFS with a visited dictionary, where false means that it has been visited but not in the current path, and true means that it has been visited and its in the |
| Minimum Score After Removals on a Tree | Graph, XOR | XOR Trick: A ^ B ^ B = A ⇒ calculating sums is easier, component 3 = total ^ component 1 ^ component 2 Brute force solution: Explore all possible combination of cut |
| Rearranging Fruits | Array | TC: O(nlogn), SC: O(n): Initialise a frequency hashmap for all excess elements in both baskets (find elements that needs to be swapped). Then check if any key has frequency that is an odd number, return -1, otherwise add the key to the array val times. Note that we can either do a swap with the smallest element with the biggest element, or use a intermediate element to do a double indirect swap, so we iterate through half of the sorted merge list and add min(x, global_min * 2) to the result, and return |
| Maximum Fruits Harvested After at Most K Steps | Sliding Window | TC: O(n), SC: O(1) Sliding window technique by iterating through all possible end positions of the window, accumulating the total for each right pointer and maintaining the maximum window size each time, by using a left pointer and checking if walking full left then right or right then left is both exceeding the number of steps, then we move left pointer up by one so the window is valid. Greedy approach, the most optimal way to walk to walking fully in one direction then move the opposite. |
| Trapping Rain Water | Two Pointer | O(n) TC and SC: Create a max height on the left and right of each ith position, and calculate the amount of water trapped in each position using min(maxLeft[i], maxRight[i]) - height[i] Optimised O(1) SC: Use two pointers to track the max walls on the left and right as we iterate through the array, works because we will calculate the amount of water trapped on the pointer with the shorter wall, since the height of the right wall does not impact the sum since the left wall is shorter |
| Find the Minimum Area to Cover All Ones II | Array | Find all the possible splits of the grid into 3 subgrids and calculate the bounding box for each subgrid Use a @cache for the helper function |