[Solution]Problem 23: Maximize coin collecting[Zillow]
Recursion, Matrix Traversal, Maximization
Problem
This question was asked by Zillow.
You are given a 2-d matrix
where each cell represents number of coins in that cell. Assuming we start at matrix[0][0]
, and can only move right or down, find the maximum number of coins you can collect by the bottom right corner.
For example, in this matrix
0 3 1 1
2 0 0 4
1 5 3 1
The most we can collect is 0 + 2 + 1 + 5 + 3 + 1 = 12 coins.
Step 1: Understand the Structures
As you read the question, it should be clear that this problem is recursive. If it’s not immediately obvious think about how we can frame it recursively, think of the maximum possible value you can obtain from any given cell. When we’re at a cell, the maximum value of coins we can obtain is the value at that cell with the maximum of the values possible from either right or down. Programmatically:
maxCoins(A,i,j)= A[i][j]+ max(maxCoins(A,i+1,j),maxCoins(A,i,j+1))
#here i and j represent positions in your matrix A.
This should make the recursive nature of the solution pretty clear. Now that we have identified the recursion, what should our next step be? It is identifying the stop case(s).
Step 2: Terminal Cases
So when does our standard recursive case end? The most obvious answer is when we hit the bottom right corner of the matrix. At this stage, we just want to return the value at our current cell (since we can’t really move on beyond that). That is our definite hard stop. But is that the only destination when we change our recursive call?
There are two other cases that we should consider. These aren’t terminal cases, since they involve recursive calls, but they are different to our main recursive call. What are these cases? Look at how our code is designed. Our code will end up at indexes that are not the bottom-right but are in either the last row or the last column. How do we deal with this? Simple.
When in the last row, we can only move right. Do that
Similarly when in the last column, move to the down.
For practice, sketch up the recursive function call to see how the base case, these cases, and the first recursive function call would interact. When you’re looking at the code shared in the end, check how you did. Using feedback is a powerful way to improve.
Step 3: Coding up the Naive Recursive Solution
It should not be difficult to put everything we have done so far so create the naive recursive solution. If you’re a regular reader, you know that I will not code it up here. Why? Because this solution is exponential runtime. My advice to you is to just lead your interviewer to this point, to make it clear that you understand everything. But don’t waste your time writing the solution because it will take up your time.
There is a caveat to this. If you’re still a beginner, I would suggest coding up the solution, just to gain additional practice. Also if you can’t come up with the optimal solution in the interview, writing out the sub-optimal one will buy you time and even provide you with insight on how you can proceed. With that said, let’s come up with the final, optimal solution.
Step 4: Optimal Solution
When figuring out how to optimize, it can be helpful to look at where the code is not optimal. Let’s take a look at how we structured our solution. Given the example array from earlier:
0 3 1 1 2 0 0 4 1 5 3 1 and the position (1,1), I want you notice something. Regardless of whether you reach (1,1) from (0,1) or from (1,0), the maximum you can collect from (1,1) is the same. Take a second to verify this for yourself. This will hold true for any index. This means that you once you have calculated the maximum from (1,1) (or any position), you don't need to recalculate it again. Instead, you just store this value and refer to it at all other times when it's required. To those of you familiar with dynamic programming, this should be ringing bells. This is indeed an application of the common dynamic programming technique, memoization. Following is a pretty cool graphic explaining the process.
But the question is still how do we memoize? And what kind of a data structure can we use to store the values? What is our final code going to look like? That’s what we’re going to go over now. Take special notes at this stage, because learning how to put all of what we’ve done together is crucial.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.