Jump Game II (Minimum Jumps)

📋

Problem

Imagine you are trying to cross a series of stepping stones across a river, but each stone lets you jump only a limited distance forward. How do you minimize the number of jumps to reach the other side?

Given an array of non-negative integers nums, where each element represents your maximum jump length at that position, return the minimum number of jumps required to reach the last index. You can assume that you can always reach the last index.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^5It is guaranteed that you can reach the last index.

Edge cases: Single element array [0] → 0 jumps neededArray with all ones [1,1,1,1] → n-1 jumps neededArray with a large jump at start [10,1,1,1] → 1 jump needed

</>

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: 1Always jumping to the furthest reachable index without incrementing jumps properly.✅ Increment jumps only when current index reaches current_end boundary.

Wrong: 0Returning zero jumps for arrays longer than one element due to missing jump increments.✅ Initialize jumps to zero and increment when index reaches current_end.

Wrong: n-1Failing to use greedy optimization, defaulting to one-step jumps always.✅ Track next_end to jump further when possible, not just one step.

Wrong: TLEUsing brute force recursion or BFS with O(2^n) or O(n^2) complexity.✅ Implement O(n) greedy approach using current_end and next_end tracking.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly.

Watch out for common greedy pitfalls and indexing errors.

Optimize your solution to linear time complexity.

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 how far you can jump from each position.

💡 Track the furthest reachable index and when to increase jump count.

💡 Use a greedy approach updating current end and next end boundaries.

Why it failed: Returned wrong jump count; likely not updating jump count when reaching current jump boundary. Fix by incrementing jumps when index reaches current_end.

✓ Correctly computed minimum jumps using greedy boundary tracking.

t1_02basic

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

Expected3

⏱ Performance - must finish in 2000ms

Jumps: 0->1, 1->3, 3->4; total 3 jumps.

💡 Check how the maximum reachable index changes as you iterate.

💡 Update jump count only when you reach the end of the current jump range.

💡 Ensure to track next_end as max of next_end and i + nums[i].

Why it failed: Incorrect jump count due to not updating next_end or jumps at correct indices. Fix by updating jumps when i == current_end and next_end tracking.

✓ Greedy approach correctly calculates minimal jumps.

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 when array length is 1.

💡 No jumps needed if start is the end.

💡 Return 0 immediately if nums length is 1.

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

✓ Correctly handles single element base case.

t2_02edge

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Check behavior when all jumps are minimal (1).

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

💡 Greedy approach should count jumps as length-1 in this case.

Why it failed: Underestimated jumps by skipping increments; fix by incrementing jumps when reaching current_end.

✓ Correctly counts jumps for uniform minimal jumps.

t2_03edge

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

Expected1

⏱ Performance - must finish in 2000ms

First jump covers entire array; only 1 jump needed.

💡 Check if first jump can reach or surpass last index.

💡 If yes, return 1 immediately.

💡 Greedy approach should detect this by next_end >= last index.

Why it failed: Returned more than 1 jump despite large first jump; fix by checking if next_end reaches last index early.

✓ Correctly handles large initial jump.

t3_01corner

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

Expected4

⏱ Performance - must finish in 2000ms

Greedy trap: jumping to furthest reachable index each time is not always minimal jumps.

💡 Beware of greedy trap: always jump to furthest reachable index.

💡 Track current_end and next_end to decide when to increment jumps.

💡 Increment jumps only when index reaches current_end, not at every step.

Why it failed: Greedy trap: incrementing jumps at every furthest reachable update causes overcount. Fix by incrementing jumps only when index == current_end.

✓ Avoids greedy trap by proper jump increment logic.

t3_02corner

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

Expected2

⏱ Performance - must finish in 2000ms

Confusion between 0/1 knapsack and jump game: cannot reuse jumps multiple times.

💡 Remember jumps are discrete steps, not cumulative sums.

💡 Do not treat jumps as unbounded moves; each jump moves forward once.

💡 Use BFS or greedy level approach, not unbounded knapsack logic.

Why it failed: Mistakenly treated jumps as unbounded moves causing wrong count. Fix by using level-based jump counting.

✓ Correctly distinguishes jump steps from unbounded moves.

t3_03corner

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

Expected0

⏱ Performance - must finish in 2000ms

Although problem guarantees reachability, test to catch off-by-one errors in indexing.

💡 Check indexing carefully to avoid off-by-one errors.

💡 Ensure loop boundaries and conditions handle last index correctly.

💡 Verify jump count increments only when needed and stops at last index.

Why it failed: Off-by-one error caused infinite loop or wrong jumps. Fix loop conditions and jump increments to handle last index properly.

✓ Handles indexing and boundaries correctly.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n) solution to complete within 2 seconds.

💡 Brute force exponential solutions will time out here.

💡 Use greedy approach with O(n) time complexity.

💡 Track current_end and next_end to minimize jumps efficiently.

Why it failed: TLE due to exponential or quadratic complexity. Fix by implementing O(n) greedy solution.

✓ Efficient O(n) solution passes performance test.

Practice

1. Consider the following Python code that computes the minimum cost to connect sticks using a min-heap. What is the value of total_cost returned when the input is [1, 8, 3, 5]?

easy

A. 30

B. 36

C. 33

D. 29

Solution

1. Step 1: Trace initial heap and first merge

   Heapify sticks: [1,3,5,8]. Pop 1 and 3 -> cost=4, total_cost=4. Push 4 back -> heap: [4,5,8]

2. Step 2: Trace second and third merges

   Pop 4 and 5 -> cost=9, total_cost=13. Push 9 -> heap: [8,9]. Pop 8 and 9 -> cost=17, total_cost=30. Push 17 -> heap: [17]. Loop ends.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of merges: 4 + 9 + 17 = 30 [OK]

Hint: Sum merges stepwise using min-heap pops [OK]

Common Mistakes:

• Adding costs incorrectly or missing last merge
• Confusing heap order or popping wrong elements
• Off-by-one in loop iterations

2. Consider the following Python function that returns the largest monotone increasing digits number less than or equal to n. What is the output when n = 332?

def monotoneIncreasingDigits(n: int) -> int:
    digits = list(map(int, str(n)))
    marker = len(digits)
    for i in range(len(digits) - 1, 0, -1):
        if digits[i] < digits[i - 1]:
            digits[i - 1] -= 1
            marker = i
    for i in range(marker, len(digits)):
        digits[i] = 9
    return int(''.join(map(str, digits)))

print(monotoneIncreasingDigits(332))

easy

A. 299

B. 329

C. 2999

D. 322

Solution

1. Step 1: Trace the loop from right to left

   Digits start as [3, 3, 2]. At i=2, digits[2]=2 < digits[1]=3, so digits[1] decrements to 2 and marker=2.

2. Step 2: Set digits from marker to end to 9

   Digits become [3, 2, 9]. Next, at i=1, digits[1]=2 < digits[0]=3, so digits[0] decrements to 2 and marker=1. Then digits from index 1 onward set to 9 -> [2, 9, 9].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final digits [2,9,9] form 299 which is largest monotone ≤ 332 [OK]

Hint: Decrement and set trailing digits to 9 for monotone fix [OK]

Common Mistakes:

• Stopping after first decrement without rechecking previous digits
• Not setting trailing digits to 9
• Returning intermediate digits without full fix

3. Consider the following Python function implementing the optimal wiggle subsequence algorithm. What is the value of count after the loop finishes when the input is [1, 5, 4]?

def wiggleMaxLength(nums):
    if not nums:
        return 0
    count = 1
    last_diff = 0
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):
            count += 1
            last_diff = diff
    return count

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace loop iterations

   Input: [1, 5, 4] - i=1: diff=5-1=4 >0 and last_diff=0 ≤0 -> count=2, last_diff=4 - i=2: diff=4-5=-1 <0 and last_diff=4 ≥0 -> count=3, last_diff=-1

2. Step 2: Final count value

   After loop, count=3, which is the length of the longest wiggle subsequence.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Count increments twice for valid wiggles [OK]

Hint: Count increments on sign change of diff from last_diff

Common Mistakes:

• Off-by-one counting
• Ignoring initial count=1
• Not updating last_diff correctly

4. What is the time complexity of the optimal greedy algorithm using a stack to remove k digits from a number string of length n to get the smallest number?

medium

A. O(n) because each digit is pushed and popped at most once

B. O(n^2) because nested loops are needed to find digits to remove

C. O(n log n) due to sorting digits internally

D. O(n * k) because each digit can cause up to k pops

Solution

1. Step 1: Identify operations per digit

   Each digit is pushed onto the stack once and can be popped at most once when a smaller digit arrives.

2. Step 2: Analyze total operations

   Since each push and pop happens at most once per digit, total operations are proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Stack operations are linear in n, no nested loops [OK]

Hint: Each digit pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming worst case k pops per digit -> O(n*k)
• Confusing with sorting complexity
• Thinking nested loops are needed

5. Suppose the problem is modified so that the input list can contain negative integers as well. Which of the following approaches correctly adapts the algorithm to handle negatives and still produce the largest concatenated number?

hard

A. Convert negatives to positive strings before sorting with the comparator, then prepend '-' to those in final output

B. Filter out negative numbers since they cannot contribute to the largest concatenation

C. Separate negatives and positives, sort positives with comparator, sort negatives by absolute value descending, then concatenate positives followed by negatives

D. Convert all numbers to strings including negatives, then sort with the same comparator comparing concatenations

Solution

1. Step 1: Recognize negatives affect ordering and concatenation semantics

   Negative numbers cannot be treated the same as positives because concatenation with '-' changes lex order.

2. Step 2: Separate positives and negatives, sort positives with original comparator, sort negatives by absolute value descending

   Concatenate positives first (largest number), then negatives to maintain largest overall concatenation.

3. Step 3: This approach preserves ordering logic and handles negatives correctly

   Other options either ignore negatives or mishandle signs causing incorrect results.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Separating and sorting by sign handles negatives correctly [OK]

Hint: Negatives require separate handling, not just string comparison [OK]

Common Mistakes:

• Treating negatives as strings directly
• Ignoring negatives
• Converting negatives to positives incorrectly