In this post, I’ll ‘think through’ an interview problem (leetcode problem 45- jump game II). Rather than just write the solution, I’ll try to show how I use tips from the first few articles in ‘Why you failed your tech interview’, (e.g. relying on the recursive assumption, drawing diagrams), to avoid getting ‘stuck’ and work my way to a solution. There might be better ways to reach the solution, (e.g. starting with breadth first search or considering a greedy solution first), but this will hopefully convey how I get to the solution, rather than just showing the solution itself.

The Problem - Leetcode 45: Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:

Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:

You can assume that you can always reach the last index.

Trying to find a recursive solution

The first thing I try to do is find a recursive solution. Suppose I am trying to write a function, $minJumps(index)$, which will return me the minimum number of jumps to get from $index$ to the end of the array (so $minJumps(0)$ would be the solution to the problem).

Let’s call the last index, $n$. Then, we have the base case that $minJumps(n) = 0$. Now, when trying to write $minJumps(k)$ for an arbitrary $k$, we can apply the recursive assumption and imagine that $minJumps(index)$ would correctly return the minimum number of jumps for any index from $k+1$ to $n$. Then, we can get the correct answer for $minJumps(k)$ by simply trying each index that we can jump to. In mathematical terms:

$minJumps(k) = \min\limits_{i \in k+1..min( k+A[k],n) } minJumps(i)$

Analyzing the recursive solution’s complexity

What kind of complexity does this lead to?

We can imagine that the code for the recursive case would be a for loop running over indices from $k+1$ to $k+A[k]$ and making a recursive call at each index. In the worst case, let’s imagine that $A[k] = n$. Then, we can see that the running time at index $k$ would be:

$T(k) = \sum_{i=k+1}^{n} T(i)$

I don’t know the exact complexity of this, but I can tell you that it’s at least exponential (given that if it were only the first two terms in the sum it would be the same as fibonacci). Much like fibonacci, we should be able to make this much better by computing it with dynamic programming.

Applying dynamic programming

Let’s imagine that we computed each recursive call from the end of the array back to the beginning and stored the result (in an auxiliary array) so that each recursive call would return in constant time. Would this reduce the overall complexity?

If we do that, our running time would be (similar to insertion sort): $\sum_{i=1}^{n}i = O(n^2)$

Certainly better than exponential, but can we do even better?

Imagining the computation, I don’t see an easy way to reduce the amount of work done.

Trying to get a recursive solution from the other direction.

Let’s try defining $minSteps(i)$ as the minimum number of steps to start at index $0$ and reach index, $i$ (the opposite of what we did before). Assume we are writing $minSteps(i)$ and then use the recursive assumption to say that $minSteps(k)$ works for all $k < i$. How do we get an answer for $minSteps(i)$?

Let’s consider each previous index, (indices from $0$ to $i-1$), and find the ones that allow us to reach index $i$, then take the best one. Mathematically: $\min\limits_{k \in 1,2,...i-1\space and\space k+A[k] \ge i } minSteps(k) + 1$ .

Let’s suppose we compute this solution using dynamic programming, what would the complexity be? For each $i$, we have to check all previous indices, so our complexity is $T(n) = \sum_{i=1}^{n}i = O(n^2)$ again.

No better than the other way.

Trying to eliminate some repeated work

Imagining how the computation for the dynamic program would proceed, I can see some repeated work. When we compute the answer for an index, $k$, we’re redoing the entire min calculation just to see which indices apply to index $k$ but not index $k-1$. Can we eliminate some of that work?

Jump game arrays

Also, if we think about it, we’ll end up filling the ‘cost’ array and it will look something like:

0,1,1,…,1,2,2,…,2,3,3,…,3,…,?,?,?,?

Maybe we can directly compute the index where we change from 0 to 1, 1 to 2, etc., i.e. find the largest index we can reach for a given number of steps?

Let’s try repeatedly computing the highest index we can reach for a given number of steps. Once that index is $>= n$, we know the minimum number of steps required (the solution).

When computing this, if we know the last 2 farthest indices, farthest index we can process in $k-1$ steps and the farthest index we can process in $k-2$ steps, we only need to check

Mathematically:

$furthestIndex(k) = \max\limits_{i \in furthestIndex(k-2) ... furthestIndex(k-1) } (A[i] + i)$

The complexity of this solution should be just $O(n)$ because we only have to look at each index in the array once.

Coding the solution

Before we code the solution, let’s draw a diagram showing what we are planning to do:

Jump game 2 solution diagram

Then, we can write our code (in python3 and with leetcode boilerplate):

class Solution(object):
    def jump(self, nums):
        farthest_reachable = 0
        num_steps = 0
        next_index = 0
        while (farthest_reachable < (len(nums) - 1)):
            new_farthest_index = farthest_reachable;
            while (next_index <= farthest_reachable and farthest_reachable < len(nums)):
                new_farthest_index = max(new_farthest_index, next_index + nums[next_index])
                next_index += 1
            num_steps += 1
            farthest_reachable = new_farthest_index
        return num_steps

This could actually be done with a single loop, but I find it easy to understand the code this way.

Before ‘submitting’ this code, I think of a loop invariant, not necessarily formally, for my loops. The first loop’s purpose is to update ‘farthest_reachable’. At the start and end of it, I should check that ‘farthest_reachable’ is the farthest index that can be reached in ‘num_steps’ and that ‘next_index’ points to the first index that isn’t processed. I personally don’t bother with the inner loop’s loop invariant, but you could also reason about that if you wanted.

Let me know in the comments below if this helped you or if you have any other questions or if there’s another interview problem you’d be interested in me thinking through.

Leetcode 45 Jump Game II - Thinking through interview problems