Solution: Jump Game

Statement

Given an array of integers called nums, each element represents a square in a game board. At each turn, the player can take up to $s$ steps toward the last square, where $s$ is the value of the current square. This means from any position, you can move forward by any number of steps from $1$ up to the value at that position. Starting at the first index, your goal is to determine whether it’s possible to reach the last index of the array. Write a function that returns TRUE if you can reach the end, or FALSE if you get stuck somewhere.

Constraints:

• $1 \leq$ nums.length $\leq 10^3$
• $0 \leq$ nums[i] $\leq 10^3$

Solution

You may have already brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and implementation constraints.

Naive approach

The naive approach is to attempt all possible jump patterns to traverse from the initial position to the final position. The process begins at the starting position and involves jumping to every reachable index. This process is repeated until the last index is reached. In case we are unable to proceed further, a backtrack is performed to explore alternative paths. This method, although inefficient, ensures that all potential paths are explored to reach the final position. However, the time complexity of the backtracking approach will be exponential.

Optimized approach using the greedy pattern

An optimized way to solve this problem is to use a greedy strategy, working backwards through the array. Instead of jumping forward and tracking all possibilities, we flip the perspective: we start at the last index (our target) and ask, “Can we reach this point from any previous position?”

Moving from the second-last index toward the start, we keep track of the leftmost position (target) that can reach the end. If an element at index i has a value large enough to jump to or past the current target, then we update our target to be i. This means that if we can reach the target, we can reach the end. We repeat this until we either reach the start of the array or find ourselves stuck with no way to reach the goal. If we finish with target == 0, the first index can eventually reach the last one, and we return TRUE. Otherwise, if target ends up beyond index 0, there’s no valid path, and we return FALSE.