Jump Game

The Problem

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.

Determine if you are able to reach the last index.

Example #1

  1. Input: [2,3,1,1,4]
  2. Output: true
  3. Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example #2

  1. Input: [3,2,1,0,4]
  2. Output: false
  3. Explanation: You will always arrive at index 3 no matter what. Its maximum
  4.              jump length is 0, which makes it impossible to reach the last index.

Naming

We call a position in the array a “good index” if starting at that position, we can reach the last index. Otherwise, that index is called a “bad index”. The problem then reduces to whether or not index 0 is a “good index”.

Solutions

Approach 1: Backtracking

This is the inefficient solution where we try every single jump pattern that takes us from the first position to the last. We start from the first position and jump to every index that is reachable. We repeat the process until last index is reached. When stuck, backtrack.

See backtrackingJumpGame.js file

Time complexity:: O(2^n). There are 2n (upper bound) ways of jumping from the first position to the last, where n is the length of array nums.

Auxiliary Space Complexity: O(n). Recursion requires additional memory for the stack frames.

Approach 2: Dynamic Programming Top-down

Top-down Dynamic Programming can be thought of as optimized backtracking. It relies on the observation that once we determine that a certain index is good / bad, this result will never change. This means that we can store the result and not need to recompute it every time.

Therefore, for each position in the array, we remember whether the index is good or bad. Let’s call this array memo and let its values be either one of: GOOD, BAD, UNKNOWN. This technique is called memoization.

See dpTopDownJumpGame.js file

Time complexity:: O(n^2). For every element in the array, say i, we are looking at the next nums[i] elements to its right aiming to find a GOOD index. nums[i] can be at most n, where n is the length of array nums.

Auxiliary Space Complexity: O(2 * n) = O(n). First n originates from recursion. Second n comes from the usage of the memo table.

Approach 3: Dynamic Programming Bottom-up

Top-down to bottom-up conversion is done by eliminating recursion. In practice, this achieves better performance as we no longer have the method stack overhead and might even benefit from some caching. More importantly, this step opens up possibilities for future optimization. The recursion is usually eliminated by trying to reverse the order of the steps from the top-down approach.

The observation to make here is that we only ever jump to the right. This means that if we start from the right of the array, every time we will query a position to our right, that position has already be determined as being GOOD or BAD. This means we don’t need to recurse anymore, as we will always hit the memo table.

See dpBottomUpJumpGame.js file

Time complexity:: O(n^2). For every element in the array, say i, we are looking at the next nums[i] elements to its right aiming to find a GOOD index. nums[i] can be at most n, where n is the length of array nums.

Auxiliary Space Complexity: O(n). This comes from the usage of the memo table.

Approach 4: Greedy

Once we have our code in the bottom-up state, we can make one final, important observation. From a given position, when we try to see if we can jump to a GOOD position, we only ever use one - the first one. In other words, the left-most one. If we keep track of this left-most GOOD position as a separate variable, we can avoid searching for it in the array. Not only that, but we can stop using the array altogether.

See greedyJumpGame.js file

Time complexity:: O(n). We are doing a single pass through the nums array, hence n steps, where n is the length of array nums.

Auxiliary Space Complexity: O(1). We are not using any extra memory.

References