Jump Game

📋

Problem

Imagine you are 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?

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, or false otherwise.

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

Edge cases: Single element array [0] → true (already at last index)Array with zeros blocking path [2,0,0] → false if zeros block all pathsArray with large jumps at start [100,0,0,0] → true (jump directly to end)

</>

IDE

def canJump(nums: list[int]) -> bool:public boolean canJump(int[] nums)bool canJump(vector<int> &nums)function canJump(nums)

def canJump(nums):
    # Write your solution here
    pass

class Solution {
    public boolean canJump(int[] nums) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool canJump(vector<int> &nums) {
    // Write your solution here
    return false;
}

function canJump(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseNot updating max reachable index correctly, causing premature failure.✅ Update maxReach = max(maxReach, i + nums[i]) and check if maxReach >= last index.

Wrong: trueIgnoring zeros that block all paths, returning true incorrectly.✅ Return false if current index > max reachable index indicating blocked path.

Wrong: falseFailing to handle single element array as trivially reachable.✅ Return true immediately if nums length is 1.

Wrong: trueGreedy trap: only checking next step instead of max reachable index.✅ Track max reachable index and ensure current index <= max reachable index.

Wrong: trueTreating zeros as always passable, ignoring blocking zeros at start.✅ Return false if nums[0] == 0 and length > 1.

✓

Test Cases

Focus on handling minimal and boundary inputs like single element and zeros.

Think about common pitfalls like greedy traps and zero-blocked paths.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"nums":[2,3,1,1,4]}

Expectedtrue

⏱ Performance - must finish in 2000ms

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

💡 Think about how far you can jump from each position.

💡 Use dynamic programming or greedy to track the furthest reachable index.

💡 Keep updating the maximum reachable index and check if it reaches the last index.

Why it failed: Returned false but path exists. Likely not updating max reachable index correctly. Fix by tracking maxReach = max(maxReach, i + nums[i]) and checking if maxReach >= last index.

✓ Correctly identifies reachable last index using max reachable position tracking.

t1_02basic

Input{"nums":[3,2,1,0,4]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Cannot jump past index 3 because nums[3] = 0 blocks progress, so last index unreachable.

💡 Check if any position blocks further jumps.

💡 Track the furthest reachable index and see if it stops before the last index.

💡 If max reachable index is less than current index at any point, return false.

Why it failed: Returned true but path blocked by zero at index 3. Fix by returning false if current index > max reachable index.

✓ Correctly detects unreachable last index due to blocking zero.

t2_01edge

Input{"nums":[0]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single element array means already at last index, so trivially reachable.

💡 Consider the smallest input size.

💡 If array length is 1, you are already at the last index.

💡 Return true immediately if nums length is 1.

Why it failed: Returned false for single element array. Fix by returning true if nums length is 1 since start is end.

✓ Correctly handles single element array as reachable.

t2_02edge

Input{"nums":[2,0,0]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Zeros block all paths beyond index 1, so cannot reach last index.

💡 Zeros can block progress if no jump can bypass them.

💡 Track max reachable index and verify it doesn't get stuck.

💡 If max reachable index stops before last index, return false.

Why it failed: Returned true despite zeros blocking path. Fix by checking if current index exceeds max reachable index and returning false.

✓ Correctly detects blocking zeros prevent reaching last index.

t2_03edge

Input{"nums":[100,0,0,0]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Large jump at start allows direct jump to last index.

💡 Large jump at start can skip intermediate zeros.

💡 Check if max reachable index reaches or exceeds last index early.

💡 Return true as soon as max reachable index >= last index.

Why it failed: Returned false despite large jump at start. Fix by updating max reachable index correctly and checking early termination condition.

✓ Correctly handles large jump at start to reach last index.

t3_01corner

Input{"nums":[1,1,0,1]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Greedy trap: naive greedy might jump step by step but get stuck at zero blocking index 2.

💡 Greedy must track max reachable index, not just next step.

💡 Check if max reachable index ever falls behind current index.

💡 Return false if current index > max reachable index.

Why it failed: Returned true due to greedy choosing next step without checking max reachable index. Fix by tracking max reachable index and validating current index <= max reachable index.

✓ Correctly avoids greedy trap by tracking max reachable index.

t3_02corner

Input{"nums":[0,2,3]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Cannot move from start if first element is zero and array length > 1.

💡 Check if first element allows any jump when length > 1.

💡 If nums[0] == 0 and length > 1, return false immediately.

💡 No moves possible from start means unreachable last index.

Why it failed: Returned true despite no moves possible from start. Fix by returning false if nums[0] == 0 and length > 1.

✓ Correctly handles zero at start blocking all progress.

t3_03corner

Input{"nums":[2,5,0,0,0,0,1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack and jump game: jumps can skip zeros if reachable.

💡 Jump game allows skipping zeros if reachable from previous jumps.

💡 Track max reachable index carefully to skip zeros.

💡 Return true if max reachable index >= last index even if zeros in between.

Why it failed: Returned false by treating zeros as impassable obstacles always. Fix by tracking max reachable index and allowing jumps over zeros.

✓ Correctly handles zeros that can be skipped by jumps.

t4_01performance

Input{"nums":[100000,99999,99998,99997,99996,99995,99994,99993,99992,99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,99981,99980,99979,99978,99977,99976,99975,99974,99973,99972,99971,99970,99969,99968,99967,99966,99965,99964,99963,99962,99961,99960,99959,99958,99957,99956,99955,99954,99953,99952,99951,99950,99949,99948,99947,99946,99945,99944,99943,99942,99941,99940,99939,99938,99937,99936,99935,99934,99933,99932,99931,99930,99929,99928,99927,99926,99925,99924,99923,99922,99921,99920,99919,99918,99917,99916,99915,99914,99913,99912,99911,99910,99909,99908,99907,99906,99905,99904,99903,99902,99901]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100 with large jumps to test O(n) greedy solution completes within 2 seconds.

💡 Brute force exponential solutions will time out here.

💡 Use O(n) greedy approach tracking max reachable index.

💡 Avoid nested loops or recursion to pass performance test.

Why it failed: Solution times out due to O(2^n) or O(n^2) complexity. Fix by implementing O(n) greedy max reachable index approach.

✓ Solution runs efficiently in O(n) time confirming optimal complexity.

Practice

1. You are given a list of daily stock prices and a maximum number of allowed transactions. You want to maximize profit by buying and selling stocks, but you cannot hold more than one stock at a time and must complete each transaction before starting another. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Divide and conquer splitting the price array and merging results

B. Greedy algorithm that buys whenever price is lower than the next day and sells the next day

C. Pure brute force recursion exploring all buy/sell combinations without memoization

D. Dynamic programming using state machines to track buy/sell states for each transaction count

Solution

1. Step 1: Understand problem constraints and limitations of greedy

   The problem limits the number of transactions and requires maximizing profit with buy/sell states, which greedy fails to handle optimally.

2. Step 2: Identify suitable algorithm

   Dynamic programming with state machines tracks holding and not holding states per transaction count, ensuring all possibilities are considered efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy fails on multiple transactions; DP state machines handle all cases [OK]

Hint: DP with states handles transaction limits optimally [OK]

Common Mistakes:

• Assuming greedy always works for stock problems

2. Consider the following code snippet implementing the Word Break problem. What is the value of dp[4] after the outer loop iteration where i = 4 completes, given s = "leetcode" and wordDict = ["leet", "code"]?

easy

A. False

B. IndexError due to substring bounds

C. Undefined, dp array not updated at i=4

D. True

Solution

1. Step 1: Trace dp array up to i=4

   dp[0] = True initially. For i=4, check lengths 4 and 4 (both words have length 4). dp[4 - 4] = dp[0] = True and s[0:4] = "leet" is in word_set, so dp[4] = True.

2. Step 2: Confirm no other conditions override dp[4]

   Once dp[4] is set True, inner loop breaks, so dp[4] remains True.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Substring "leet" found and dp[0] True -> dp[4] True [OK]

Hint: dp[i] is True if any dp[i-length] True and substring in dict [OK]

Common Mistakes:

• Off-by-one errors in substring indices
• Forgetting to break inner loop after True
• Assuming dp[4] remains False initially

3. Consider the following buggy code for minimum cost climbing stairs. Which line contains the subtle bug that causes incorrect results on some inputs?

medium

A. Line 4: Loop range starting at 2

B. Line 7: Returning prev1 instead of min(prev1, prev2)

C. Line 6: Updating prev2 and prev1

D. Line 3: Initialization of prev2 and prev1

Solution

1. Step 1: Understand final return logic

   The top can be reached from either last step or second last step, so minimum of prev1 and prev2 must be returned.

2. Step 2: Identify incorrect return

   Returning only prev1 ignores the possibility that prev2 might be cheaper, causing wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Return min(prev1, prev2) to cover both possible last steps [OK]

Hint: Return min of last two costs, not just last [OK]

Common Mistakes:

• Forgetting min at return
• Misinitializing base cases
• Incorrect loop boundaries

4. If the problem is changed to allow unlimited transactions instead of at most two, which modification to the DP approach is correct?

hard

A. Keep the same DP with k=2 but run the loop more times

B. Use a simpler DP tracking only holding and not holding states without transaction count

C. Use the same code but reset profit and maxDiff arrays after every two transactions

D. Use brute force to check all possible transaction pairs

Solution

1. Step 1: Understand unlimited transactions impact

   With unlimited transactions, tracking transaction count is unnecessary; only holding or not holding states matter.

2. Step 2: Simplify DP states

   Use a DP that tracks max profit holding stock or not holding stock each day, allowing multiple buys and sells without limit.

3. Step 3: Reject other options

   Keeping k=2 or resetting arrays is incorrect; brute force is inefficient and unnecessary.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Unlimited transactions reduce problem to simpler state machine [OK]

Hint: Unlimited transactions remove need to track transaction count [OK]

Common Mistakes:

• Trying to reuse k=2 DP for unlimited
• Resetting DP arrays incorrectly

5. Suppose the climbing stairs problem is modified so you can climb 1, 2, or 3 steps at a time. Which of the following changes to the space-optimized DP solution correctly computes the number of ways to reach the top?

hard

A. Keep two variables and update current as sum of the previous two only

B. Use three variables to store ways for last three steps and update current as their sum

C. Use recursion without memoization to handle the extra step size

D. Use a greedy approach to always take 3 steps when possible

Solution

1. Step 1: Understand the new step sizes

   With steps of size 1, 2, or 3, the number of ways to reach step i depends on the sum of ways to reach i-1, i-2, and i-3.

2. Step 2: Adjust space-optimized DP variables

   We need to track the last three computed values, so three variables are required to update current as their sum.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Summing last three states matches the new recurrence [OK]

Hint: Number of variables equals max step size for space optimization [OK]

Common Mistakes:

• Using only two variables for three-step jumps
• Recursion without memoization causes inefficiency