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 fixed transaction fee for each sale. You want to maximize your profit by buying and selling stocks any number of times, but you must pay the fee each time you sell. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A dynamic programming approach using state machines to track holding and not holding states with transaction fees accounted for.

B. A divide-and-conquer approach that splits the price array and merges results to find maximum profit.

C. A greedy algorithm that buys whenever the price drops and sells whenever the price rises above the previous buy price plus fee.

D. A simple linear scan that sums all positive price differences minus the fee once at the end.

Solution

1. Step 1: Understand problem constraints

   The problem requires accounting for transaction fees on each sale and multiple buy-sell operations, which greedy or simple linear scans cannot optimally handle.

2. Step 2: Identify suitable algorithm

   Dynamic programming with state machines tracks two states: holding stock and not holding stock, updating profits while subtracting fees on sales, ensuring optimal decisions at each step.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   State machine DP correctly models fee impact and multiple transactions [OK]

Hint: Transaction fees require state tracking, not greedy [OK]

Common Mistakes:

• Assuming greedy always works
• Ignoring fee impact on each sale

2. Consider the following Python code implementing the optimal solution for the House Robber II problem. What is the final output when the input is [2, 3, 2]?

def rob_linear(nums, start, end):
    prev, curr = 0, 0
    for i in range(start, end + 1):
        prev, curr = curr, max(curr, prev + nums[i])
    return curr

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    return max(rob_linear(nums, 0, n - 2), rob_linear(nums, 1, n - 1))

print(rob([2,3,2]))

easy

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Trace rob_linear(nums, 0, 1)

   nums[0]=2, nums[1]=3 Iteration i=0: prev=0, curr=0 -> prev=0, curr=max(0,0+2)=2 Iteration i=1: prev=2, curr=max(2,0+3)=3 Return 3

2. Step 2: Trace rob_linear(nums, 1, 2)

   nums[1]=3, nums[2]=2 Iteration i=1: prev=0, curr=0 -> prev=0, curr=max(0,0+3)=3 Iteration i=2: prev=3, curr=max(3,0+2)=3 Return 3 Max(3,3) = 3

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both cases yield 3, final output is 3 [OK]

Hint: Trace both linear cases and pick max [OK]

Common Mistakes:

• Off-by-one in loop range
• Confusing which subarray to use
• Incorrect max calculation

3. You are given an array where each element represents the maximum jump length from that position. Your goal is to reach the last index in the minimum number of jumps. Which algorithmic approach guarantees finding the minimum number of jumps efficiently?

easy

A. A greedy approach that tracks the furthest reachable index and increments jumps when the current range ends

B. A depth-first search with memoization caching minimum jumps from each position

C. A bottom-up dynamic programming approach that fills a dp array with minimum jumps to each index

D. A brute force recursion exploring all jump paths

Solution

1. Step 1: Understand problem constraints and goal

   The problem requires finding the minimum number of jumps to reach the last index efficiently.

2. Step 2: Evaluate algorithmic approaches

   Brute force recursion explores all paths but is exponential and inefficient. DFS with memoization improves but still can be costly. Bottom-up DP solves the problem in O(n^2) time. The greedy approach runs in O(n) time by tracking the furthest reachable index and incrementing jumps only when the current range ends, guaranteeing the minimum jumps.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy approach is optimal and runs in linear time [OK]

Hint: Greedy tracks furthest reachable and increments jumps at range end [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing greedy with bottom-up DP
• Thinking DFS with memo is always best

4. Suppose the House Robber II problem is modified so that you can rob the same house multiple times (i.e., unlimited reuse), but still cannot rob two adjacent houses in the same night. Which of the following approaches correctly adapts the solution to this variant?

hard

A. Since houses can be robbed multiple times, simply sum all house values ignoring adjacency

B. Modify rob_linear to consider robbing the current house multiple times by adding nums[i] repeatedly in the recurrence

C. Use the same DP but allow adding nums[i] multiple times in rob_linear without changing adjacency checks

D. Use a DP that tracks states with and without robbing the current house, allowing reuse but skipping adjacent houses, effectively a modified linear DP with state transitions

Solution

1. Step 1: Understand the reuse constraint

   Robbing the same house multiple times requires tracking states to ensure no two adjacent houses are robbed in the same iteration.

2. Step 2: Modify DP to track states

   DP must track whether the previous house was robbed to prevent adjacency, allowing multiple robberies over time but not consecutively.

3. Step 3: Reject naive summation or repeated addition

   Simply adding nums[i] multiple times or ignoring adjacency breaks problem constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stateful DP with adjacency checks handles reuse correctly [OK]

Hint: Track rob/no-rob states to handle reuse with adjacency [OK]

Common Mistakes:

• Ignoring adjacency when reusing houses
• Trying to add nums[i] repeatedly without state
• Summing all values ignoring constraints

5. Suppose the Word Break problem is modified so that dictionary words can be reused unlimited times in the segmentation. Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Change dp array to store counts of ways to segment instead of booleans

B. No change needed; the original DP already supports unlimited reuse of words

C. Remove the break statement after setting dp[i] = True to consider all segmentations

D. Use a recursive backtracking approach without memoization to explore all reuse possibilities

Solution

1. Step 1: Understand the reuse requirement

   Unlimited reuse means counting all possible segmentations, not just checking existence.

2. Step 2: Modify DP to count ways

   Change dp from boolean to integer counts, summing counts from dp[i - length] when substring is in dictionary.

3. Step 3: Evaluate other options

   Original DP only checks existence (boolean), removing break doesn't count ways correctly, recursion without memoization is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting ways requires dp to store counts, not booleans [OK]

Hint: Counting segmentations requires dp to store counts, not booleans [OK]

Common Mistakes:

• Assuming original DP counts ways
• Removing break to count ways incorrectly
• Using naive recursion without memoization