Jump Game (Can Reach End?)

🎯

Jump Game (Can Reach End?)

mediumGREEDYAmazonMicrosoftFacebook

Imagine you're playing a video game where you can jump forward on platforms, but each platform limits how far you can jump next. Can you reach the last platform?

💡 This problem tests your ability to reason about how far you can move forward step-by-step. Beginners often struggle because they try to explore all paths instead of tracking the maximum reachable position efficiently.

📋

Problem Statement

Given an array of non-negative integers nums, where each element represents your maximum jump length at that position, determine if you can reach the last index starting from the first index. Return true if you can reach the last index, otherwise false.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^5

💡

Example

Input"[2,3,1,1,4]"

Outputtrue

Start at index 0, jump 1 step to index 1, then jump 3 steps to the last index.

Input"[3,2,1,0,4]"

Outputfalse

You will get stuck at index 3 because nums[3] = 0 and cannot move forward.

• Single element array [0] → true (already at last index)
• Array with zeros blocking path [1,0,1] → false
• Array with large jumps at start [100,0,0,0] → true
• Array where last jump is zero but reachable [2,5,0,0,0] → true

⚠️

Common Mistakes

Not checking if current index is beyond max reachable index

Incorrectly returns true even when stuck

✅ Add a condition to return false if current index > maxReach

Using recursion without memoization on large inputs

Stack overflow or timeout

✅ Add memoization or switch to iterative greedy

Updating maxReach incorrectly (e.g., not taking max)

Misses reachable indices, returns false incorrectly

✅ Always update maxReach = max(maxReach, i + nums[i])

Not handling single-element arrays correctly

May return false when should return true

✅ Check base case where array length is 1

🧠

Brute Force (Backtracking / Recursion)

💡 This approach explores every possible jump from each position, helping beginners understand the problem's exhaustive nature before optimizing.

Intuition

From each index, try all possible jumps within the allowed range and recursively check if the end can be reached.

Algorithm

1. Start from index 0.
2. From current index, try all jumps from 1 to nums[current].
3. Recursively check if any jump leads to the last index.
4. If any path reaches the end, return true; otherwise, false.

💡 This approach is straightforward but inefficient because it tries all paths without remembering results.

</>

Code

def canJump(nums):
    def backtrack(position):
        if position == len(nums) - 1:
            return True
        furthest_jump = min(position + nums[position], len(nums) - 1)
        for next_pos in range(position + 1, furthest_jump + 1):
            if backtrack(next_pos):
                return True
        return False

    return backtrack(0)

# Example usage
if __name__ == '__main__':
    print(canJump([2,3,1,1,4]))  # True
    print(canJump([3,2,1,0,4]))  # False

Line Notes

def backtrack(position):Defines recursive helper to explore jumps from current position

if position == len(nums) - 1:Base case: reached last index successfully

furthest_jump = min(position + nums[position], len(nums) - 1)Calculate max jump boundary to avoid index overflow

for next_pos in range(position + 1, furthest_jump + 1):Try every possible jump from current position

if backtrack(next_pos):If any recursive call returns true, propagate success

return FalseNo jump leads to end from this position

public class Solution {
    public boolean canJump(int[] nums) {
        return backtrack(nums, 0);
    }

    private boolean backtrack(int[] nums, int position) {
        if (position == nums.length - 1) return true;
        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPos = position + 1; nextPos <= furthestJump; nextPos++) {
            if (backtrack(nums, nextPos)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.canJump(new int[]{2,3,1,1,4})); // true
        System.out.println(sol.canJump(new int[]{3,2,1,0,4})); // false
    }
}

Line Notes

public boolean canJump(int[] nums)Entry method to start recursion from index 0

if (position == nums.length - 1) return true;Base case: reached last index

int furthestJump = Math.min(position + nums[position], nums.length - 1);Calculate max jump boundary safely

for (int nextPos = position + 1; nextPos <= furthestJump; nextPos++)Try all jumps from current position

if (backtrack(nums, nextPos)) return true;Return true if any path reaches end

return false;No path from this position leads to end

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool backtrack(const vector<int>& nums, int position) {
        if (position == (int)nums.size() - 1) return true;
        int furthestJump = min(position + nums[position], (int)nums.size() - 1);
        for (int nextPos = position + 1; nextPos <= furthestJump; ++nextPos) {
            if (backtrack(nums, nextPos)) return true;
        }
        return false;
    }

    bool canJump(vector<int>& nums) {
        return backtrack(nums, 0);
    }
};

int main() {
    Solution sol;
    vector<int> test1 = {2,3,1,1,4};
    vector<int> test2 = {3,2,1,0,4};
    cout << boolalpha << sol.canJump(test1) << endl; // true
    cout << boolalpha << sol.canJump(test2) << endl; // false
    return 0;
}

Line Notes

bool backtrack(const vector<int>& nums, int position)Recursive helper to explore jumps from current position

if (position == (int)nums.size() - 1) return true;Base case: reached last index

int furthestJump = min(position + nums[position], (int)nums.size() - 1);Calculate max jump boundary safely

for (int nextPos = position + 1; nextPos <= furthestJump; ++nextPos)Try all possible jumps from current position

if (backtrack(nums, nextPos)) return true;Return true if any path reaches end

return false;No path from this position leads to end

function canJump(nums) {
    function backtrack(position) {
        if (position === nums.length - 1) return true;
        let furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (let nextPos = position + 1; nextPos <= furthestJump; nextPos++) {
            if (backtrack(nextPos)) return true;
        }
        return false;
    }
    return backtrack(0);
}

// Example usage
console.log(canJump([2,3,1,1,4])); // true
console.log(canJump([3,2,1,0,4])); // false

Line Notes

function backtrack(position)Recursive helper to explore jumps from current position

if (position === nums.length - 1) return true;Base case: reached last index

let furthestJump = Math.min(position + nums[position], nums.length - 1);Calculate max jump boundary safely

for (let nextPos = position + 1; nextPos <= furthestJump; nextPos++)Try all possible jumps from current position

if (backtrack(nextPos)) return true;Return true if any path reaches end

return false;No path from this position leads to end

⏱

Complexity

TimeO(2^n) in worst case

SpaceO(n) due to recursion stack

At each position, we try all possible jumps, leading to an exponential number of paths.

💡 For n=20, this could mean over a million recursive calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is valuable to understand the problem's exhaustive nature.

🧠

Top-Down Memoization (Recursion + Cache)

💡 Memoization avoids recomputing results for the same positions, improving efficiency while keeping the recursive structure.

Intuition

Store results of subproblems (positions) to avoid repeated work when exploring jumps recursively.

Algorithm

1. Create a cache to store if a position can reach the end.
2. Start recursion from index 0.
3. If position is cached, return cached result.
4. Try all jumps from current position; cache and return true if any succeed.
5. If none succeed, cache and return false.

💡 Memoization prunes the recursion tree by remembering results, making the algorithm much faster.

</>

Code

def canJump(nums):
    n = len(nums)
    memo = [None] * n

    def backtrack(position):
        if position == n - 1:
            return True
        if memo[position] is not None:
            return memo[position]
        furthest_jump = min(position + nums[position], n - 1)
        for next_pos in range(position + 1, furthest_jump + 1):
            if backtrack(next_pos):
                memo[position] = True
                return True
        memo[position] = False
        return False

    return backtrack(0)

# Example usage
if __name__ == '__main__':
    print(canJump([2,3,1,1,4]))  # True
    print(canJump([3,2,1,0,4]))  # False

Line Notes

memo = [None] * nInitialize cache to store results for each position

if memo[position] is not None:Return cached result if already computed

memo[position] = TrueCache success when a path from this position reaches end

memo[position] = FalseCache failure when no path from this position reaches end

return backtrack(0)Start recursion from index 0

import java.util.Arrays;

public class Solution {
    private Boolean[] memo;

    public boolean canJump(int[] nums) {
        memo = new Boolean[nums.length];
        return backtrack(nums, 0);
    }

    private boolean backtrack(int[] nums, int position) {
        if (position == nums.length - 1) return true;
        if (memo[position] != null) return memo[position];
        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPos = position + 1; nextPos <= furthestJump; nextPos++) {
            if (backtrack(nums, nextPos)) {
                memo[position] = true;
                return true;
            }
        }
        memo[position] = false;
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.canJump(new int[]{2,3,1,1,4})); // true
        System.out.println(sol.canJump(new int[]{3,2,1,0,4})); // false
    }
}

Line Notes

private Boolean[] memo;Cache to store results for each position

if (memo[position] != null) return memo[position];Return cached result if available

memo[position] = true;Cache success when path found

memo[position] = false;Cache failure when no path found

return backtrack(nums, 0);Start recursion from index 0

#include <iostream>
#include <vector>
using namespace std;

class Solution {
    vector<int> memo; // -1 unknown, 0 false, 1 true
public:
    bool backtrack(const vector<int>& nums, int position) {
        if (position == (int)nums.size() - 1) return true;
        if (memo[position] != -1) return memo[position] == 1;
        int furthestJump = min(position + nums[position], (int)nums.size() - 1);
        for (int nextPos = position + 1; nextPos <= furthestJump; ++nextPos) {
            if (backtrack(nums, nextPos)) {
                memo[position] = 1;
                return true;
            }
        }
        memo[position] = 0;
        return false;
    }

    bool canJump(vector<int>& nums) {
        memo.assign(nums.size(), -1);
        return backtrack(nums, 0);
    }
};

int main() {
    Solution sol;
    vector<int> test1 = {2,3,1,1,4};
    vector<int> test2 = {3,2,1,0,4};
    cout << boolalpha << sol.canJump(test1) << endl; // true
    cout << boolalpha << sol.canJump(test2) << endl; // false
    return 0;
}

Line Notes

vector<int> memo;Cache vector to store results: -1 unknown, 0 false, 1 true

if (memo[position] != -1) return memo[position] == 1;Return cached result if known

memo[position] = 1;Cache success when path found

memo[position] = 0;Cache failure when no path found

memo.assign(nums.size(), -1);Initialize cache with unknown state

function canJump(nums) {
    const n = nums.length;
    const memo = new Array(n).fill(null);

    function backtrack(position) {
        if (position === n - 1) return true;
        if (memo[position] !== null) return memo[position];
        let furthestJump = Math.min(position + nums[position], n - 1);
        for (let nextPos = position + 1; nextPos <= furthestJump; nextPos++) {
            if (backtrack(nextPos)) {
                memo[position] = true;
                return true;
            }
        }
        memo[position] = false;
        return false;
    }

    return backtrack(0);
}

// Example usage
console.log(canJump([2,3,1,1,4])); // true
console.log(canJump([3,2,1,0,4])); // false

Line Notes

const memo = new Array(n).fill(null);Initialize cache array with null to mark unknown states

if (memo[position] !== null) return memo[position];Return cached result if available

memo[position] = true;Cache success when path found

memo[position] = false;Cache failure when no path found

return backtrack(0);Start recursion from index 0

⏱

Complexity

TimeO(n^2) in worst case

SpaceO(n) for recursion stack and memo

Memoization prunes repeated calls but still may explore many jumps per position.

💡 For n=1000, this reduces calls drastically compared to brute force but can still be slow.

Interview Verdict: Accepted but not optimal

This approach is a good improvement but can time out on very large inputs.

🧠

Greedy (Tracking Maximum Reachable Index)

💡 This approach uses a single pass to track the furthest reachable index, making it optimal and intuitive once understood.

Intuition

Keep track of the maximum index reachable so far. If at any point the current index is beyond this max reach, return false. If max reach reaches or passes the last index, return true.

Algorithm

1. Initialize maxReach to 0.
2. Iterate through the array indices.
3. If current index is greater than maxReach, return false (stuck).
4. Update maxReach to max(maxReach, current index + nums[current index]).
5. If maxReach reaches or exceeds last index, return true.

💡 This approach is efficient because it only needs one pass and no recursion or extra space.

</>

Code

def canJump(nums):
    maxReach = 0
    for i, jump in enumerate(nums):
        if i > maxReach:
            return False
        maxReach = max(maxReach, i + jump)
        if maxReach >= len(nums) - 1:
            return True
    return False

# Example usage
if __name__ == '__main__':
    print(canJump([2,3,1,1,4]))  # True
    print(canJump([3,2,1,0,4]))  # False

Line Notes

maxReach = 0Initialize max reachable index to start

for i, jump in enumerate(nums):Iterate over each position and jump length

if i > maxReach:If current position is beyond max reachable, stuck and return false

maxReach = max(maxReach, i + jump)Update max reachable index

if maxReach >= len(nums) - 1:If we can reach or pass last index, return true

public class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) return false;
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.canJump(new int[]{2,3,1,1,4})); // true
        System.out.println(sol.canJump(new int[]{3,2,1,0,4})); // false
    }
}

Line Notes

int maxReach = 0;Initialize max reachable index

for (int i = 0; i < nums.length; i++)Iterate through each index

if (i > maxReach) return false;If current index is unreachable, return false

maxReach = Math.max(maxReach, i + nums[i]);Update max reachable index

if (maxReach >= nums.length - 1) return true;Return true if end is reachable

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (i > maxReach) return false;
            maxReach = max(maxReach, i + nums[i]);
            if (maxReach >= (int)nums.size() - 1) return true;
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> test1 = {2,3,1,1,4};
    vector<int> test2 = {3,2,1,0,4};
    cout << boolalpha << sol.canJump(test1) << endl; // true
    cout << boolalpha << sol.canJump(test2) << endl; // false
    return 0;
}

Line Notes

int maxReach = 0;Initialize max reachable index

for (int i = 0; i < (int)nums.size(); ++i)Iterate through each index

if (i > maxReach) return false;If current index is unreachable, return false

maxReach = max(maxReach, i + nums[i]);Update max reachable index

if (maxReach >= (int)nums.size() - 1) return true;Return true if end is reachable

function canJump(nums) {
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) return true;
    }
    return false;
}

// Example usage
console.log(canJump([2,3,1,1,4])); // true
console.log(canJump([3,2,1,0,4])); // false

Line Notes

let maxReach = 0;Initialize max reachable index

for (let i = 0; i < nums.length; i++)Iterate through each index

if (i > maxReach) return false;If current index is unreachable, return false

maxReach = Math.max(maxReach, i + nums[i]);Update max reachable index

if (maxReach >= nums.length - 1) return true;Return true if end is reachable

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array, updating max reachable index without extra space.

💡 For n=10^5, this means 100,000 operations, which is efficient for interviews.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews due to its simplicity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the greedy approach after explaining brute force and memoization briefly.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Memoization	O(n^2)	O(n) recursion stack + O(n) memo	Possible on large inputs	Yes, with extra tracking	Good to mention as optimization
3. Greedy	O(n)	O(1)	No	No (without extra tracking)	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to grasp the problem, then move to memoization, and finally master the greedy approach for optimal performance.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force recursive approach to show understanding.Step 3: Discuss memoization to optimize repeated computations.Step 4: Present the greedy solution as the optimal approach.Step 5: Code the greedy solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize naive solutions, and knowledge of greedy algorithms.

Common Follow-ups

• What if you need the minimum number of jumps? → Use a BFS or DP approach.
• Can you reconstruct the path of jumps? → Track indices during greedy or DP.

💡 These follow-ups test your ability to extend the problem and apply related algorithms.

🔍

Pattern Recognition

When to Use

1) Problem involves jumping or moving forward in an array; 2) Need to check reachability; 3) Input size is large; 4) Problem hints at maximum reach or coverage.

Signature Phrases

maximum jump lengthcan you reach the last indexjump forward

NOT This Pattern When

Problems asking for shortest path or counting ways often require DP or BFS, not greedy.

Similar Problems

Jump Game II - find minimum jumps instead of yes/noMinimum Number of Jumps to Reach End - similar greedy or DPFrog Jump - jump with constraints, also reachability

Practice

1. You are given an array representing daily stock prices. You want to maximize profit by making as many buy-sell transactions as you like, but you must sell before you buy again. Which algorithmic approach guarantees the optimal total profit?

easy

A. Greedy approach summing all positive price differences between consecutive days

B. Dynamic Programming with memoization to explore all buy-sell pairs

C. Single pass to find the maximum single buy-sell pair profit

D. Divide and conquer to split the array and combine profits

Solution

1. Step 1: Understand the problem constraints

   The problem allows unlimited transactions but requires selling before buying again, so multiple buy-sell pairs can be combined.

2. Step 2: Identify the approach that captures all profitable segments

   Summing all positive consecutive day price differences captures every profitable transaction, ensuring maximum total profit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Summing positive differences matches the optimal profit for all test cases [OK]

Hint: Sum all positive consecutive price differences [OK]

Common Mistakes:

• Trying to find only one best buy-sell pair
• Using complex DP when greedy suffices
• Ignoring multiple transactions allowed

2. Given the following code and input, what is the final returned total cost?

def twoCitySchedCost(costs):
    costs.sort(key=lambda x: x[0] - x[1])
    n = len(costs) // 2
    total = 0
    for i, cost in enumerate(costs):
        if i < n:
            total += cost[0]
        else:
            total += cost[1]
    return total

costs = [[10,20],[30,200],[400,50],[30,20]]
print(twoCitySchedCost(costs))

easy

A. 110

B. 150

C. 120

D. 140

Solution

1. Step 1: Sort costs by difference cost[0] - cost[1]

   Differences: [10-20=-10, 30-200=-170, 400-50=350, 30-20=10]. Sorted: [[30,200], [10,20], [30,20], [400,50]]

2. Step 2: Assign first half to city A, rest to city B and sum costs

   First two: city A costs = 30 + 10 = 40; last two: city B costs = 20 + 50 = 70; total = 40 + 70 = 110

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum matches manual calculation [OK]

Hint: Sort by difference, assign first half to city A [OK]

Common Mistakes:

• Misordering after sorting by difference
• Off-by-one in loop boundary
• Adding wrong city cost for last half

3. Consider the following buggy code for partitioning labels. Which line contains the subtle bug that can cause incorrect partitions?

def partitionLabels(s):
    last = [0] * 26
    for i, c in enumerate(s):
        last[ord(c) - ord('a')] = i
    res = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        end = last[ord(c) - ord('a')]  # Bug here: missing max()
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

medium

A. Line 3: Updating last occurrence map

B. Line 13: Calculating partition size with end - start + 1

C. Line 8: Initializing end to 0

D. Line 11: Updating end without taking max

Solution

1. Step 1: Understand role of end variable

   End must track the furthest last occurrence of any character seen so far to avoid premature partitioning.

2. Step 2: Identify bug in updating end

   Assigning end directly to last occurrence of current character without max() loses track of previous furthest last occurrence, causing incorrect partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing max() causes partitions to cut too early [OK]

Hint: Always update end = max(end, last[c]) [OK]

Common Mistakes:

• Forgetting max() when updating partition end
• Off-by-one errors in partition size calculation
• Not precomputing last occurrences

4. What is the time complexity of the optimal greedy solution for Two City Scheduling that sorts by cost difference and assigns people in a single pass?

medium

A. O(n^2) because of nested loops to assign people

B. O(n log n) due to sorting the list of 2n people

C. O(n) since assignment is done in one pass after sorting

D. O(n log n) including sorting and constant time assignment

Solution

1. Step 1: Identify sorting cost

   Sorting 2n people by cost difference takes O(n log n) time.

2. Step 2: Identify assignment cost

   Assigning people in a single pass is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting dominates, total complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity [OK]

Common Mistakes:

• Assuming assignment is nested loop causing O(n^2)
• Ignoring sorting cost and claiming O(n)
• Confusing space complexity with time complexity

5. Suppose the problem is modified so that children can have equal ratings but must still have strictly more candies than neighbors with lower ratings. Which modification to the optimal algorithm correctly handles this variant?

hard

A. Change comparison from '>' to '>=' in both passes to handle equal ratings

B. Keep '>' comparisons but initialize candies with zeros and adjust accordingly

C. Use the same two-pass greedy with '>' comparisons but do not update candies if ratings are equal

D. Replace two-pass greedy with a sorting-based approach to assign candies in rating order

Solution

1. Step 1: Understand new requirement

   Children with equal ratings do not require more candies than each other, only strictly higher ratings require more candies.

2. Step 2: Adjust comparisons in algorithm

   Keep '>' comparisons to ensure only strictly higher ratings get more candies; do not update candies when ratings are equal.

3. Step 3: Avoid changing to '>=' which would incorrectly increase candies for equal ratings

   Changing to '>=' breaks minimality and correctness.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Strict '>' comparisons preserve problem constraints with equal ratings [OK]

Hint: Strict '>' comparisons handle equal ratings correctly [OK]

Common Mistakes:

• Changing '>' to '>=' causing over-assignment
• Initializing candies with zeros
• Using sorting unnecessarily