Scale Engineer

Jump Game

Med
#0055Time: O(2^n)Space: O(n)34 companies
Patterns
Dynamic ProgrammingGreedy
Data structures
Array
Companies
AdobeAmazonAppleBloomberg

Prompt

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

Approaches

3 approaches with complexity analysis and trade-offs.

This approach is a straightforward brute-force method. We simulate all possible jump combinations recursively. Starting from the first index, we explore every possible jump. If any of these paths lead to the last index, we return true.

Algorithm

  • Define a recursive function canJumpFromPosition(position, nums).
  • If position is the last index, return true.
  • Calculate the furthest reachable index from position: furthestJump = position + nums[position].
  • Iterate from position + 1 to furthestJump.
  • For each nextPosition, recursively call canJumpFromPosition(nextPosition, nums).
  • If the recursive call returns true, return true.
  • If the loop finishes without finding a path, return false.
  • The initial call is canJumpFromPosition(0, nums).

Walkthrough

The core idea is a recursive function, say canJumpFrom(position, nums), which checks if the end can be reached from a given position.

  • Base Case: If position is the last index (nums.length - 1), we've successfully reached the end, so we return true.

  • Recursive Step: From the current position, we can jump to any index from position + 1 up to position + nums[position]. We iterate through all these possible next positions. For each nextPosition, we make a recursive call canJumpFrom(nextPosition, nums). If any of these recursive calls return true, it means we've found a valid path, and we can return true immediately.

  • Failure: If we try all possible jumps from the current position and none of them lead to a solution (i.e., all recursive calls return false), it means the end is not reachable from this position. We then return false.

This method explores all possible jump paths from the starting position, which can lead to a large number of redundant calculations.

class Solution {    public boolean canJump(int[] nums) {        return canJumpFromPosition(0, nums);    }     private boolean canJumpFromPosition(int position, int[] nums) {        if (position >= nums.length - 1) {            return true;        }         int furthestJump = nums[position];        // Iterate backwards from the furthest jump for a slight optimization        // as longer jumps are more likely to reach the end faster.        for (int jump = furthestJump; jump >= 1; jump--) {            if (canJumpFromPosition(position + jump, nums)) {                return true;            }        }         return false;    }}

Complexity

Time

O(2^n)

Space

O(n)

Trade-offs

Pros

  • Conceptually simple and easy to implement.

Cons

  • Extremely inefficient due to re-computation of the same subproblems.

  • Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.

Solutions

public class Solution {    public bool CanJump(int[] nums) {        int mx = 0;        for (int i = 0; i < nums.Length; ++i) {            if (mx < i) {                return false;            }            mx = Math.Max(mx, i + nums[i]);        }        return true;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem