Jump Game II (Min Jumps)

📋

Jump Game II (Min Jumps)

Edge cases:

</>

IDE

def jump(nums: list[int]) -> int:public int jump(int[] nums)int jump(vector<int> nums)function jump(nums)

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

class Solution {
    public int jump(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int jump(vector<int> nums) {
    // Write your solution here
    return 0;
}

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

Common Bugs to Avoid

Wrong: 1Incorrectly returning 1 jump for input [2,3,1,1,4], missing the second jump.✅ Increment jumps only when current index exceeds previous max reach, not at every step.

Wrong: 0Returning 0 jumps for arrays longer than 1, failing to count any jumps.✅ Return 0 only if array length is 1; otherwise count jumps properly.

Wrong: 4Counting each step as a jump even when longer jumps are possible.✅ Update jumps only when current index passes previous max reach, not at every index.

Wrong: TLEUsing O(n^2) or exponential brute force approach on large inputs.✅ Implement O(n) greedy approach tracking max reachable index and jumps.

Wrong: Incorrect jump count on zerosTreating zeros as blockers without considering reachability from previous jumps.✅ Track max reachable index properly to bypass zeros if reachable.

✓

Test Cases

Focus on handling base cases and small arrays correctly before moving on.

Think about common pitfalls like greedy traps and zero blockers in jump logic.

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

t1_01basic

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

Expected2

⏱ Performance - must finish in 2000ms

Jump 1 step from index 0 to 1, then 3 steps to the last index.

💡 Think about the minimum jumps needed to reach each position.

💡 Use dynamic programming or greedy to track the farthest reachable index at each step.

💡 Update the jump count only when you move beyond the current maximum reach.

Why it failed: Returned wrong jump count; likely failed to update jumps when reaching the current max reach. Fix by incrementing jumps only when current index exceeds previous max reach.

✓ Correctly computed minimum jumps using DP or greedy approach.

t1_02basic

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

Expected3

⏱ Performance - must finish in 2000ms

Jump from index 0 to 1, then to 3, then to last index 4.

💡 Track the farthest reachable index and jumps needed as you iterate.

💡 Update jumps count only when you move beyond the current coverage.

💡 Ensure to consider all reachable indices within current jump range.

Why it failed: Incorrect jump count; probably incremented jumps too early or too late. Fix by incrementing jumps exactly when current index passes previous max reach.

✓ Correctly handled jumps for varying step sizes.

t2_01edge

Input{"nums":[0]}

Expected0

⏱ Performance - must finish in 2000ms

Single element array requires zero jumps as already at last index.

💡 Consider the base case where array length is 1.

💡 No jumps needed if start is already at the last index.

💡 Return 0 immediately if nums length is 1.

Why it failed: Returned non-zero jumps for single element array; fix by returning 0 when nums length is 1.

✓ Correctly handled single element base case.

t2_02edge

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

Expected3

⏱ Performance - must finish in 2000ms

Each jump moves exactly one step; total jumps = length - 1 = 3.

💡 When all steps are 1, jumps equal array length minus one.

💡 Check if your logic handles uniform step sizes correctly.

💡 Ensure jump count increments at each step until last index.

Why it failed: Returned fewer jumps than length-1 for all ones array; fix by counting each step as a jump.

✓ Correctly counted jumps for uniform step sizes.

t2_03edge

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

Expected3

⏱ Performance - must finish in 2000ms

Jump from index 0 to 3, then to 4; zero in middle does not block if reachable. Minimum jumps is 3.

💡 Zeros in the array do not always block progress if reachable from previous jumps.

💡 Check if your solution handles zeros correctly when reachable.

💡 Ensure jumps consider maximum reachable indices, not just next step.

Why it failed: Failed to handle zeros reachable by earlier jumps; fix by tracking max reachable index properly.

✓ Correctly handled zeros that are reachable.

t2_04edge

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

Expected1

⏱ Performance - must finish in 2000ms

Large jump at start allows reaching end in one jump.

💡 Check if your solution handles large jumps at start correctly.

💡 Ensure jump count is minimal when first jump can reach or surpass last index.

💡 Update jumps count only when necessary.

Why it failed: Returned more than 1 jump despite large initial jump; fix by checking if first jump reaches end.

✓ Correctly handled large initial jump.

t3_01corner

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

Expected3

⏱ Performance - must finish in 2000ms

Optimal jumps: from index 0 to 1, then from 1 to last index 6.

💡 Beware of greedy traps where jumping to farthest reachable index is not always optimal.

💡 Check if your solution tries all reachable indices or just the farthest.

💡 Use DP or greedy with careful max reach and jump count updates.

Why it failed: Greedy approach failed by jumping too far too early; fix by updating jumps only when current index exceeds previous max reach.

✓ Correctly avoided greedy trap by proper jump counting.

t3_02corner

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

Expected2

⏱ Performance - must finish in 2000ms

Must jump from 0->2->4; zeros are bypassed by reachable jumps. Minimum jumps is 3.

💡 Do not confuse jump game with knapsack problems; jumps are sequential.

💡 Zeros can be bypassed if reachable from previous jumps.

💡 Track max reachable index and increment jumps accordingly.

Why it failed: Incorrectly treated zeros as blockers; fix by tracking max reachable index properly.

✓ Correctly handled zeros and jump logic.

t3_03corner

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

Expected1

⏱ Performance - must finish in 2000ms

Large jump at start allows reaching end in one jump.

💡 Check if your solution handles large jumps at start correctly.

💡 Ensure jump count is minimal when first jump can reach or surpass last index.

💡 Update jumps count only when necessary.

Why it failed: Returned more than 1 jump despite large initial jump; fix by checking if first jump reaches end.

✓ Correctly handled large initial jump.

t4_01performance

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

Expectednull

⏱ Performance - must finish in 2000ms

n=100,000, O(n) greedy approach must complete within 2 seconds.

💡 Brute force or O(n^2) DP will time out on large inputs.

💡 Use a linear greedy approach tracking max reachable index and jumps.

💡 Increment jumps only when current index passes previous max reach.

Why it failed: TLE due to O(n^2) or exponential complexity; fix by implementing O(n) greedy solution.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. You are given a list of daily stock prices and want to maximize profit by buying and selling stocks with the constraint that after selling a stock, you must wait one day before buying again. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Brute force recursion exploring all buy/sell/cooldown sequences without memoization

B. A greedy algorithm that buys at every local minimum and sells at every local maximum

C. Dynamic programming with state machine to track holding, cooldown, and free states

D. Divide and conquer splitting the price array into subproblems and merging results

Solution

1. Step 1: Understand the cooldown constraint

   The cooldown day after selling prevents immediate rebuying, which breaks greedy local min/max approaches.

2. Step 2: Recognize the need for state tracking

   Dynamic programming with states (holding, cooldown, free) models the problem accurately and efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy fails on cooldown; DP state machine handles it correctly [OK]

Hint: Cooldown requires state tracking, not greedy [OK]

Common Mistakes:

• Assuming greedy local min/max works despite cooldown
• Ignoring cooldown day after selling

2. You are given a circular street with houses arranged in a loop, each containing some amount of money. You want to maximize the amount you rob without robbing two adjacent houses, and since the street is circular, the first and last houses are also adjacent. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that always picks the house with the maximum money first

B. Dynamic programming by splitting the problem into two linear subproblems excluding either the first or last house

C. Brute force recursion checking all subsets of houses

D. Sorting houses by money and robbing every other house

Solution

1. Step 1: Understand circular adjacency constraint

   The first and last houses cannot both be robbed, so the problem is not a simple linear DP.

2. Step 2: Split into two linear problems

   By considering two cases--rob houses from first to second last, or from second to last--we reduce the circular problem to two linear House Robber problems solvable by DP.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Splitting into two linear DP subproblems handles circular adjacency correctly [OK]

Hint: Split circular problem into two linear DP cases [OK]

Common Mistakes:

• Assuming greedy or sorting works
• Trying to rob first and last house together
• Using brute force without pruning

3. Given the following code for minimum cost climbing stairs, what is the value of curr during the first iteration of the loop when cost = [10, 15, 20]?

easy

A. 30

B. 25

C. 20

D. 15

Solution

1. Step 1: Initialize variables

   prev2 = cost[0] = 10, prev1 = cost[1] = 15

2. Step 2: Calculate curr at i=2

   curr = cost[2] + min(prev1, prev2) = 20 + min(15, 10) = 20 + 10 = 30

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   curr is sum of current cost plus min of previous two costs [OK]

Hint: curr = cost[i] + min(prev1, prev2) at each iteration [OK]

Common Mistakes:

• Mixing prev1 and prev2 values
• Off-by-one errors in loop
• Returning intermediate curr instead of final min

4. The following code attempts to compute the maximum profit with transaction fee but contains a subtle bug:

def maxProfit(prices, fee):
    cash, hold = 0, -prices[0]
    for price in prices[1:]:
        cash = max(cash, hold + price)  # Bug here: fee not subtracted
        hold = max(hold, cash - price)
    return cash

What is the bug in this code?

medium

A. The hold update uses cash before it is updated in the same iteration.

B. The initial hold value should be zero instead of -prices[0].

C. The fee is not subtracted when selling stock, causing overestimated profit.

D. The loop should start from prices[0], not prices[1:].

Solution

1. Step 1: Identify where fee is applied

   The fee must be subtracted when selling stock, i.e., when updating cash.

2. Step 2: Locate bug in code

   cash update line adds hold + price but misses subtracting fee, leading to inflated profit.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing fee subtraction causes incorrect profit calculation [OK]

Hint: Fee must be subtracted exactly when selling [OK]

Common Mistakes:

• Forgetting fee on sell
• Incorrect initial hold value

5. Suppose the problem is modified so that you can reuse the same stock multiple times within a single transaction (i.e., buy and sell multiple times without waiting). Which modification to the DP approach correctly handles this variant?

hard

A. Modify the DP to allow buying again without decrementing transactions_left when holding a stock

B. Increase k to a very large number and use the unlimited transactions solution shortcut

C. Use the same DP but skip updating buy states to avoid multiple buys

D. Use a greedy approach to sum all positive price differences without DP

Solution

1. Step 1: Understand the reuse variant

   Reusing stock within a transaction means multiple buys/sells without reducing transaction count on buys.

2. Step 2: Modify DP state transitions

   Allow buy state updates without decrementing transactions_left, so holding state can be refreshed multiple times per transaction.

3. Step 3: Why other options fail

   Unlimited transactions shortcut ignores transaction limit; skipping buy updates breaks profit calculation; greedy fails with transaction constraints.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct DP modification respects transaction count and allows multiple buys per transaction [OK]

Hint: Allow buy updates without reducing transactions_left [OK]

Common Mistakes:

• Using unlimited transactions shortcut incorrectly
• Skipping buy updates breaks DP correctness