Array
* [ ] Two Sum * [ ] Best Time to Buy and Sell Stock * [ ] Product of Array Except Self * [ ] Maximum Subarray * [ ] Contains Duplicates * [ ] Maximum Product Subarray * [ ] Search in Rotated Sorted Array * [ ] 3Sum * [ ] Container With Most Water * [ ] Sliding Window Maximum :triangular\_flag\_on\_post:String
* [ ] Valid Anagram * [ ] Valid Palindrome * [ ] Longest Substring Without Repeating Characters * [ ] Longest Repeating Character Replacement * [ ] Find All Anagrams in a String :triangular\_flag\_on\_post: * [ ] Minimum Window Substring * [ ] Group Anagrams :triangular\_flag\_on\_post: * [ ] Longest Palindromic Substring :triangular\_flag\_on\_post: * [ ] Encode and Decode Strings :star:Hash Table
* [ ] Two Sum * [ ] Ransom Note * [ ] Group Anagrams * [ ] Insert Delete GetRandom O(1) :triangular\_flag\_on\_post: * [ ] First Missing Positive :triangular\_flag\_on\_post: * [ ] LRU Cache :triangular\_flag\_on\_post: * [ ] All O\`one Data Structure :triangular\_flag\_on\_post:Recursion
* [ ] Generate Parentheses :triangular\_flag\_on\_post: * [ ] Combinations * [ ] Subsets * [ ] Letter Combinations of a Phone Number * [ ] Subsets 2 * [ ] Permutations * [ ] Sudoku Solver :triangular\_flag\_on\_post: * [ ] Strobogrammatic Number 2 :star:Sorting and Searching
* [ ] Binary Search * [ ] Search in Rotated Sorted Array * [ ] Kth Smallest Element in a Sorted Matrix :triangular\_flag\_on\_post: * [ ] Search a 2D Matrix * [ ] Kth Largest Element in an Array * [ ] Find Minimum in Rotated Sorted Array * [ ] Median of Two Sorted Arrays :triangular\_flag\_on\_post:Matrix
* [ ] Set Matrix Zeroes * [ ] Spiral Matrix :triangular\_flag\_on\_post: * [ ] Rotate Image * [ ] Valid Sudoku :triangular\_flag\_on\_post:Linked List
* [ ] Reverse a Linked List * [ ] Detect Cycle in a Linked List * [ ] Merge Two Sorted Lists * [ ] Merge K Sorted Lists * [ ] Remove Nth Node From End of List * [ ] Reorder ListQueue
* [ ] Implement Stack using Queues * [ ] Implement Queue using Stacks * [ ] Design Circular Queue * [ ] Design Hit Counter :star:Stack
* [ ] Valid Parentheses * [ ] Implement Queue using Stacks * [ ] Implement Stack using Queues * [ ] Min Stack * [ ] Asteroid Collision * [ ] Evaluate Reverse Polish Notation * [ ] Basic Calculator :triangular\_flag\_on\_post: * [ ] Basic Calculator 2 :triangular\_flag\_on\_post: * [ ] Daily Temperature * [ ] Trapping Rain Water :triangular\_flag\_on\_post: * [ ] Largest Rectangle in Histogram :triangular\_flag\_on\_post:Tree
* [ ] Same Tree * [ ] Binary Tree Maximum Path Sum :triangular\_flag\_on\_post: * [ ] Binary Tree Level Order Traversal * [ ] Lowest Common Ancestor of a Binary Tree * [ ] Binary Tree Right Side View * [ ] Subset of Another Tree :triangular\_flag\_on\_post: * [ ] Construct Binary Tree from Preorder and Inorder Traversal :triangular\_flag\_on\_post: * [ ] Serialize and Deserialize Binary Tree :triangular\_flag\_on\_post: * [ ] Validate Binary Search Tree :triangular\_flag\_on\_post: * [ ] Kth Smallest Element in a BSTGraph
* [ ] Number of Islands * [ ] Flood Fill * [ ] 01 Matrix * [ ] Rotting Oranges * [ ] Minimum Knight Moves :star: * [ ] Clone Graph * [ ] Pacific Atlantic Water Flow :triangular\_flag\_on\_post: * [ ] Number of Connected Components in an Undirected Graph :star: * [ ] Graph Valid Tree :star: * [ ] Course Schedule * [ ] Alien Dictionary :star:Heap
* [ ] Merge K Sorted Lists * [ ] K Closest Points to Origin * [ ] Top K Frequent Elements * [ ] Find Median from Data Stream :triangular\_flag\_on\_post:Trie
* [ ] Implement Trie (Prefix Trie) * [ ] Add and Search Word * [ ] Word Break :triangular\_flag\_on\_post: * [ ] Word Search 2 :triangular\_flag\_on\_post:Interval
* [ ] Merge Intervals * [ ] Insert Intervals * [ ] Non-overlapping Intervals * [ ] Meeting Rooms :star: * [ ] Meeting Rooms 2 :star:Dynamic Programming
For more questions on Dynamic Programming, refer to the [#dynamic-programming-roadmap](#dynamic-programming-roadmap "mention") after you are done with this initial study plan * [ ] Climbing Stairs * [ ] Coin Change * [ ] House Robber * [ ] Longest Increasing Subsequence * [ ] 0/1 Knapsack or Partition Equal Subset Sum * [ ] Longest Common Subsequence * [ ] Word Break * [ ] Combination Sum * [ ] House Robber 2 * [ ] Decode Ways * [ ] Unique Paths * [ ] Jump GameBinary
* [ ] Sum of Two Integers * [ ] Number of 1 bits * [ ] Counting Bits * [ ] Missing Number * [ ] Reverse Bits * [ ] Single NumberMath
* [ ] Pow(x, n) * [ ] Sqrt(x) * [ ] Integer to English WordsGeometry
* [ ] Rectangle Overlap * [ ] K Closest Points to Origin * [ ] Rectangle AreaWarmup
* [ ] Climbing Stairs * [ ] Nth Tribonacci Number * [ ] Perfect SquaresLinear Sequences
These are problems that require solving sub-problems based on the prefix of the array with a constant transition * [ ] Minimum Cost to Climb Stairs * [ ] Minimum Time to Make Rope Colorful :triangular\_flag\_on\_post: * [ ] House Robber * [ ] Decode Ways * [ ] Minimum Cost for Tickets :triangular\_flag\_on\_post: * [ ] Solving Questions with BrainpowerGrids
These are problems where the dynamic programming array is the same dimensions as the grid * [ ] Unique Paths * [ ] Unique Paths 2 :triangular\_flag\_on\_post: * [ ] Minimum Path Sum * [ ] Count Square Submatrices with All Ones :triangular\_flag\_on\_post: * [ ] Maximal Square * [ ] Dungeon Game :triangular\_flag\_on\_post:Two Sequences
These problems often require $$O(MN)$$, where $$dp\[i]\[j]$$ solves for $$arr1\[:i]$$ and $$arr2\[:j]$$ * [ ] Longest Common Subsequence * [ ] Uncrossed Lines * [ ] Minimum ASCII Delete Sum for Two Strings * [ ] Edit Distance * [ ] Distinct Subsequences * [ ] Shortest Common SupersequenceIntervals
These problems often require solving for every interval of the array * [ ] Longest Palindromic Subsequnce * [ ] Strong Game 7 :triangular\_flag\_on\_post: * [ ] Palindromic Substrings * [ ] Minimum Cost Tree from Leaf Values * [ ] Strange Pointer * [ ] Burst BalloonsLinear Sequence Transitions
These problems are often solved on every prefix of the array, transition from every $$j < i$$ * [ ] Count Number of Teams * [ ] Longest Increasing Subsequence * [ ] Partition Array for Maximum Sum * [ ] Largest Sum of Averages * [ ] Filling Bookcase ShelvesKnapsack-like
* [ ] Partition Equal Subset Sum * [ ] Number of Dice Rolls with Target Sum * [ ] Combination Sum 4 * [ ] Ones and Zeros * [ ] Coin Change * [ ] Coin Change 2 * [ ] Target Sum * [ ] Last Stone Weight 2 * [ ] Profitable SchemesTopological Sort/Graphs
These problems often require solving on all sub-graphs connected to each node * [ ] Longest String Chain * [ ] Longest Increasing Path in a Matrix * [ ] Course Schedule 3Trees
These problems often require solving on all subtrees * [ ] House Robbers 3 :triangular\_flag\_on\_post: * [ ] Binary Tree CamerasInteresting Problems
Other interesting problems that I have done so far * [ ] String Compression 2 :triangular\_flag\_on\_post: * [ ] Minimum Difficulty of a Job Schedule :triangular\_flag\_on\_post:
| Algorithm | Time Complexity | Space Complexity | Remarks |
|---|---|---|---|
| BFS | O(E + V) | O(V) | |
| DFS | O(E + V) | O(V) | Space accounting for stack frames used in recursion |
| Topological Sorting | O(E + V) | O(V) for storing the edges and frontier | Note that when iterating over every node, we only decrease the edges at most O(E) times |
| Dijkstra | O((V + E) \log V) | O(E) for priority queue | |
| Bellman-Ford | O(EV) | For O(V) vertices, we iterate through all O(E) edges and compute the SSP | |
| Prim’s Algorithm | O(E \log V) or O(V^2) | Time complexity achieved if using Fibonacci heap AND iterating over the entire priority queue | |
| Kruskal’s Algorithm | O(E \log V) |
Some states rely on multiple previously computed state. This contrasts the $$n$$ state caching optimization as $$n$$ is not fixed. {% endhint %} ## Bottom-up ```python def perfect_squares(n): dp = {} for i in range(1, n + 1): # we want to iterate from [1, n] root = i**0.5 if int(root)**2 == i: dp[i] = 1 else: p = 1 dp[i] = 10**9 # we set it to 10^9 because we are using min() while p**2 < i: dp[i] = min(dp[i], 1 + dp[i - p**2]) p += 1 return dp[n] ``` {% hint style="success" %} **Trick:** using impossibly high/low numbers to initialize $$dp(i)$$\ \ If `min(dp[i], ...)` is used, then use an impossibly high number to initialize `dp[i]`\ \ Otherwise, if `max(dp[i], ...)` is used, then use an impossibly low number or `0` if no other states can be `0`. {% endhint %} # Linear Sequence In general, the problems under this category fall under a similar problem scope as [Perfect Squares](/problems-guide/dynamic-programming-roadmap/warmup/perfect-squares) where the optimal answer can usually acquired by solving for every prefix/suffix of the array and then using the previously computed past states to compute the current state. This is a combination of the trick to "re-frame the problem" and the recurrence pattern of "past states". # Min Cost to Climb Stairs ## Observations * On each step `n`, we must incur the cost since we have to decide whether or not to move one or two steps up * To reach step `n`, you must move from step `n - 1` or step `n - 2` * To minimize the cost to reach step `n`, we need to minimize the cost it takes to reach it ## Recurrence relation $$ dp(n) = \begin{cases} cost(0), n = 0\\ cost(1), n = 1\\ \min(dp(n-1),dp(n-2)) + cost(n) \end{cases} $$ We can define $$dp(n)$$ as the minimum cost it takes to climb from step $$n$$. If we start at the first step, the cost is $$cost(0)$$ and if we start at the second step, the cost is $$cost(1)$$. Otherwise, for every step $$n$$, the cost to climb from it is the cost it took to reach it with the cost of leaving the step. ## Bottom-up The $$n$$ state caching optimization can be applied here again, given that each state depends only on the previous 2 states. ```python def climb_stairs(costs): s1, s2 = costs[0], costs[1] for i in range(2, len(costs)): s1, s2 = s2, min(s1, s2) + costs[i] return min(s1, s2) ``` # Minimum Time to Make Rope Colorful {% hint style="info" %} There is are approaches that uses [Arrays](/data-structures/arrays#two-pointers) or greedy instead but I will not cover those. {% endhint %} ## Clarification Consecutive balloons do not count the popped balloons, so popping the middle `R` in `RRR` will still violate the criteria of having no consecutive colors. ## Observations Let's start with an arbitrary rope with balloons: `RRRGGBB` and an arbitrary cost of `[2, 1, 5, 3, 4, 1, 2]`. From hand-simulation, we know that the ultimate "optimal" answer is `XXRXGBX` where `X` are the popped balloons. 1. For every segment of like colors, we never pop the highest cost balloon to achieve the lowest possible cost within the segment (the mathematical proof is relatively easy to come up with) 2. When encountering a same color, a decision between popping the current balloon or the previously seen, unpopped, same balloon should be made, with the decision made to be the smallest of the two (see (1)) 3. For every segment of same color, once a balloon encountered is of a different color, there's no need to pop anymore of the previous color so the color tracked can be changed ## Recurrence relation $$ dp(i) = \begin{cases} dp(i-1), r\[i] \neq r\[prev]\\ dp(i-1)+\min(time\[i], time\[prev]) \end{cases} $$ `prev` is needed alongside the recurrence. Processing from left to right, $$dp(i)$$ can be interpreted as the minimum time to make the rope $$r\[:i+1]$$ colorful. This means we are solving for the prefix of the array. If $$r\[i]$$ is the same as the previous color, we need to make the decision to pop based on observation (1) using the minimum between the current cost to pop and the cost to pop the previous same color balloon. If $$r\[i]$$ is not the same, then we simply need to update the "previous color" and we know that $$dp(i) = dp(i-1)$$ since there is no balloons to pop. ## Bottom-up We will apply the $$n$$ state caching optimization, where $$n = 1$$, only storing the previous time to make the rope colorful as $$t$$. ```python def min_time(r, time): n = len(time) t = 0 prev = 0 for i in range(1, n): if r[i] == r[prev]: t += min(time[i], time[prev]) if time[prev] < time[i]: prev = i # since we pop the prev balloon, we have a new prev else: prev = i # we don't need to track the same color anymore return t ``` # House Robber ## Transitions 1. Robber chooses to rob the current house 2. Robber does not rob the current house ## Top-down The naive top-down approach would be trying all possibilities given the transitions: ```python def house_robber(houses): def rob(i): if i >= len(houses): return 0 return max(rob(i + 1), rob(i + 2) + houses[i]) return rob(0) ``` If house `i` isn't robbed, then we can move on to house `i + 1` to try again. If house `i` is robbed, then we can only start robbing from house `i + 2` onwards. This generates the following recurrence relation: $$ dp(i) = \begin{cases} 0, i >= |houses|\\ \max(dp(i+1), dp(i+2)+houses\[i]) \end{cases} $$ ## Deriving bottom-up We will apply the trick of "re-framing the problem" to derive a bottom-up solution. Given a prefix of $$i-1$$ houses, can the optimal answer for house `i` be derived? To rob house `i`, we must do so when we had not robbed the previous house, thus, we must have robbed at most house `i - 2`. If house `i` is not going to be robbed, then the most amount of money we can rob from house `0` to `i` is the same as if we only looked out houses `0` to `i - 1`. As a result, we can form a new recurrence relation: $$ dp(i) = \begin{cases} houses\[0], i =0\\ \max(houses\[0], houses\[1]), i = 1\\ \max(dp(i-1), dp(i-2)+houses\[i]) \end{cases} $$ The base cases arise from the following observations: 1. If you only have 1 house, the optimal choice is always to rob it 2. If you have 2 houses, you can either rob the first but not the second or rob the second but not the first so we pick the maximum of the two ## Bottom-up We will apply the $$n$$ state caching optimization where $$n = 2$$. ```python def house_robber(houses): if len(houses) == 1: return houses[0] h1, h2 = houses[0], max(houses[0], houses[1]) for i in range(2, len(houses)): h1, h2 = h2, max(h2, h1 + houses[i]) return h2 ``` Note that `h1` corresponds to `dp(i-2)` and `h2` corresponds to `dp(i-1)`. # Decode Ways ## Transitions 1. If `s[i] = '0'` , then invalid ways (0) 2. If `s[i] = '1'`, then we can choose to take `s[i]` as it is, or pair it with the next digit (no matter what, it will form a valid number) 3. If `s[i] = '2'`, then we can choose to take `s[i]` as it is, or pair it with the next digit as long as the next digit is from `'0'` to `'6'` 4. Any other digits have to be taken as it is ## Top-down Modelling the transitions as-is gives us: $$ dp(i) = \begin{cases} 0, s\[i] = 0\\ 1, i \geq |s|\\ dp(i+1), s\[i] \not \in \[1,2]\\ dp(i+1) + dp(i+2), s\[i] = 1 \lor (s\[i] = 2 \land s\[i+1] < 6) \end{cases} $$ ```python def decode_ways(s): def ways(i): if i >= len(s): return 1 if s[i] == '0': return 0 ans = ways(i + 1) if i + 1 < len(s) and (s[i] == '1' or (s[i] == '2' and s[i + 1] <= '6')): ans += ways(i + 2) return ans return ways(0) ``` We can then memoize the value of each recursive call by index `i`. ## Bottom-up To solve this problem using bottom-up, let's re-frame the problem. However, notice that we cannot use the prefix of the array. This is because if we were to use the prefix `s[:i+1]`, we would need to look-ahead to `s[i+1]`, which should not be available yet. So we can re-framing the problem using suffixes instead: > Given $$\[i, n)$$, can we find out how many ways there are to form $$s\[i-1]$$? {% hint style="success" %} **Trick:** Implementing recurrence relations\ \ If the recurrence relation looks like $$dp(i) = dp(i - 1)$$, then it must be processed from left to right using prefixes. If it looks like $$dp(i) = dp(i + 1)$$, then it must be processed from right to left using suffixes. {% endhint %}
| Type | Pros | Cons |
|---|---|---|
| UUID |
|
|
| ID |
|
|