[Solution]Problem 23: Maximize coin collecting[Zillow]

Recursion, Matrix Traversal, Maximization

Feb 03, 2022

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.

What would our memoization structure look like? There are two aspects to this- what do we store, and how do we store it? What we noticed was that the maximum amount collectible from an index was constant. Furthermore, the maximum total coins collected would then just become

maxCoins upto index + maxCoins from index

Thus, it makes sense to store the value from our current index. The second question becomes- how do we store this value? We want to minimize storage and maximize performance. Since we will look up the value from index multiple times, it makes the most sense t want something with constant time lookup. Here you have two choices:

Use a hashmap. The key is the index (i,j) and the value is the max value from this index.
Use a matrix with identical dimensions to our input one. Matrix[i][j] is the max value from i,j.

Either one works. They are identical in performance. I use the hashmap because it generalizes better to other memoization problems, but it’s a matter of preference here. For practice, try both ways.

def collect_coins(matrix, r=0, c=0, cache={}):
    
    num_rows = len(matrix)
    num_cols = len(matrix[0])

    is_bottom = r == num_rows - 1
    is_rightmost = c == num_cols - 1

    if (r, c) not in cache:

        if is_bottom and is_rightmost:
            cache[r, c] = matrix[r][c]
        elif is_bottom:
            cache[r, c] = matrix[r][c] + collect_coins(matrix, r, c + 1, cache)
        elif is_rightmost:
            cache[r, c] = matrix[r][c] + collect_coins(matrix, r + 1, c, cache)
        else:
            cache[r, c] = matrix[r][c] + max(collect_coins(matrix, r + 1, c, cache),
                                             collect_coins(matrix, r, c + 1, cache))

    return cache[r, c]

Here, we are traversing through the matrix. Thus the time complexity is O(M*N). Similarly, our space is O(M*N).

There is an extension to this problem, that lets us use no extra space and the same time complexity. That involves modifying the input array. If you’re interested, I can tackle that for the next post. Let me know in the comments below.

Final: O(MN) time and o(MN) space

Bonuses/Promotion (Get Free Stuff)

To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.

For most of my students, mock interviews have been very helpful. Enough mock interview practice is the key between getting that job offer and rejection. If you can get three people to become paying subscribers to this newsletter, you win a free mock interview. This offer has no upper limit, so the more subs you can get, the more mock interviews you win.

To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter: