Learning a model solution gives you a tool to solve problems of a particular type. If you write and study a model solution for binary search, you’ll be able to solve straightforward binary search problems. Doing the same thing with other common solution types will make you better than average at coding interview problems.
But not every problem matches a standard solution approach. Hard problems require non-trivial insights, and even Medium problems often need customized solutions that build on top of a standard approach. So, while knowing model solutions will give you a head start, it won’t be enough to tackle every problem confidently. After mastering the model solution for a problem type, the next step is to learn how someone discovered that solution.
Dynamic Programming (DP) provides a good example of the difference between knowing how to solve a problem and knowing how to discover the solution. Consider the LeetCode DP problem House Robber. The scenario: A robber is planning to rob a row of houses and they know how much money is in each house. If they’re not allowed to rob two adjacent houses, what is the maximum amount of money they can steal?
This problem has a short solution, though it’s not simple to come up with. The idea is to track two values, dp1 and dp2, which both start at 0. We move through the houses from left to right. dp2 always stores the current maximum amount, the best answer we have found so far. dp1 stores the previous value of dp2 — i.e., the second best answer. At each house, we add that house’s amount to the second best answer, dp1 and see if it beats the best answer, dp2. If so, it becomes the new dp2. If not, we stay with our current dp2. Since we can’t use adjacent houses, we’re not allowed to add the current house’s value to dp2 to get an even larger amount.
To implement this algorithm, we loop through the house list and execute a modified swap operation at each house. At the end, we return the best result, dp2.
for each house in houseList
temp = dp1
dp1 = dp2
dp2 = max(dp2, temp + house)
return dp2
House Robber is worth studying as a model solution because it shows how we can find an optimal solution for an entire row of houses while only considering three values: the current house amount and two sums. We don’t need to remember any previous values, so we only need O(1) space. And since we only process the list once, we only need O(n) time. Quite an efficient algorithm.
This problem is a good example of a kind of Dynamic Programming, and you can apply the solution to other problems. But although the algorithm is simple, it may not be clear how we would invent it from scratch. That’s why we want to consider how to analyze a DP problem, not just how to solve it. We’ll look at that process in the next tip.
This year, I’m publishing a series of tips for effective LeetCode practice. To read the tips in order, start with A Project for 2023.