Jump Game (Can Reach End?)

📋

Problem

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?

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

Edge cases: Single element array [0] → true (already at last index)Array with zeros blocking path [1,0,1] → falseArray with large jumps at start [100,0,0,0] → true

</>

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: falseFailing to update or track the maximum reachable index correctly.✅ Update maxReach = max(maxReach, i + nums[i]) and check if i <= maxReach during iteration.

Wrong: trueNot detecting when the path is blocked by zeros and maxReach stops short.✅ Return false if current index exceeds maxReach before reaching last index.

Wrong: trueConfusing 0/1 jump constraint, returning true when start position cannot move.✅ Return false if nums[0] == 0 and length > 1.

Wrong: falseOff-by-one error in jump range calculation causing premature failure.✅ Use inclusive range min(i + nums[i], last_index) when calculating furthest jump.

Wrong: TLEUsing exponential or quadratic backtracking instead of O(n) greedy approach.✅ Implement single pass greedy maxReach tracking to achieve O(n) time complexity.

✓

Test Cases

Focus on handling edge cases like single element arrays and zeros that block jumps.

Watch out for tricky greedy traps and off-by-one errors in your implementation.

Optimize your solution to O(n) time complexity 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 tracking the furthest index you can reach as you iterate.

💡 Use a greedy approach to update the maximum reachable index at each step.

💡 If at any point your current index is beyond the maximum reachable, return false.

Why it failed: Returned false incorrectly - likely failed to update or check max reachable index properly. Fix by ensuring maxReach = max(maxReach, i + nums[i]) and check i <= maxReach.

✓ Correctly tracks maximum reachable index and returns true when last index is reachable.

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; last index unreachable.

💡 Check if your max reachable index ever reaches or exceeds the last index.

💡 Remember to stop early if current index exceeds max reachable index.

💡 Return false if you get stuck before reaching the last index.

Why it failed: Returned true incorrectly - likely did not detect when progress is blocked by zero jumps. Fix by returning false if current index > maxReach.

✓ Correctly identifies blocked path and returns false.

t2_01edge

Input{"nums":[0]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single element array; already at last index, so return true.

💡 Consider the base case when array length is 1.

💡 If you start at the last index, no jumps needed.

💡 Return true immediately if nums length is 1.

Why it failed: Returned false incorrectly - failed to handle single-element base case. Fix by returning true if nums length is 1.

✓ Correctly handles single-element array as reachable.

t2_02edge

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Jump from index 0 to 1, but nums[1] = 0 blocks further progress; last index unreachable.

💡 Check if zeros block your path and prevent further jumps.

💡 Update max reachable index carefully and verify if you get stuck.

💡 Return false if current index exceeds max reachable index.

Why it failed: Returned true incorrectly - did not detect zero blocking path. Fix by checking if current index > maxReach and returning false.

✓ Correctly detects blocked path due to zero and returns false.

t2_03edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Large jump at start allows reaching last index immediately.

💡 Verify that large jumps at start can reach the end regardless of zeros later.

💡 Max reachable index should be updated to at least last index early.

💡 Return true if maxReach >= last index at any point.

Why it failed: Returned false incorrectly - failed to update maxReach correctly with large initial jump. Fix by maxReach = max(maxReach, i + nums[i]).

✓ Correctly handles large initial jumps and returns true.

t3_01corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Greedy trap: maxReach stops at index 5, cannot reach last index 6.

💡 Beware of greedy traps where maxReach stops before last index.

💡 Check if maxReach ever reaches or exceeds last index.

💡 Return false if current index exceeds maxReach before last index.

Why it failed: Returned true incorrectly - greedy trap bug: did not detect maxReach stopping short. Fix by checking i <= maxReach in loop.

✓ Correctly detects greedy trap and returns false.

t3_02corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

0/1 confusion: cannot jump from index 0 as nums[0] = 0 and length > 1.

💡 Remember you start at index 0 and must jump forward.

💡 If nums[0] = 0 and length > 1, you cannot move.

💡 Return false if you cannot move from start and length > 1.

Why it failed: Returned true incorrectly - confused 0/1 jump constraint. Fix by returning false if nums[0] == 0 and length > 1.

✓ Correctly handles 0/1 jump constraint and returns false.

t3_03corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Off-by-one error test: can jump from index 0 to last index directly.

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

💡 Ensure furthest jump calculation includes last index.

💡 Return true if maxReach >= last index.

Why it failed: Returned false incorrectly - off-by-one bug in jump range calculation. Fix by using min(i + nums[i], last_index) inclusive.

✓ Correctly handles off-by-one and returns true.

t4_01performance

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

Expectednull

⏱ Performance - must finish in 2000ms

n=100000, O(n) greedy solution must complete within 2 seconds.

💡 Use a single pass greedy approach to track max reachable index.

💡 Avoid recursion or nested loops to prevent TLE.

💡 Update maxReach and check feasibility in O(n) time.

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

✓ Algorithm runs in O(n) time confirming efficient complexity.

Practice

1. You have a sequence of children standing in a line, each with a rating. You must distribute candies such that each child has at least one candy, and any child with a higher rating than an immediate neighbor gets more candies than that neighbor. Which algorithmic approach guarantees the minimum total candies distributed?

easy

A. Two-pass greedy: first left-to-right to satisfy left neighbors, then right-to-left to satisfy right neighbors

B. Brute force repeated adjustment until no changes occur

C. Single pass greedy from left to right only, assigning candies based on previous child

D. Dynamic programming with memoization over all subsequences

Solution

1. Step 1: Understand the problem constraints

   Each child must have at least one candy, and children with higher rating than neighbors must have more candies.

2. Step 2: Identify algorithm that satisfies both left and right neighbor constraints

   Two-pass greedy first ensures left neighbor condition, then right neighbor condition, guaranteeing minimal total candies.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two passes ensure both neighbor constraints met [OK]

Hint: Two passes needed to satisfy both neighbors [OK]

Common Mistakes:

• Using single pass left-to-right misses right neighbor constraints
• Assuming brute force is efficient enough
• Confusing DP with greedy here

2. Given the following code, what is the return value when gas = [2, 3, 4] and cost = [3, 4, 3]?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    if sum(net) < 0:
        return -1
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

print(canCompleteCircuit(gas, cost))

easy

A. -1

B. 0

C. 1

D. 2

Solution

1. Step 1: Compute net array

   net = [2-3, 3-4, 4-3] = [-1, -1, 1], sum(net) = -1 which is less than 0, so return -1 immediately.

2. Step 2: Check sum(net)

   Since sum(net) < 0, no start station can complete the circuit.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of net gas is negative, no solution exists [OK]

Hint: Sum net gas < 0 means no solution [OK]

Common Mistakes:

• Forgetting to check total gas vs cost
• Misindexing prefix sums
• Returning wrong start index

3. You are given a string and need to rearrange its characters so that no two adjacent characters are the same. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm using a max heap (priority queue) to always pick the most frequent character available next

B. Dynamic Programming that counts character frequencies and tries all permutations

C. Simple sorting of characters and placing them in alternating positions without frequency checks

D. Backtracking by generating all permutations and checking adjacency constraints

Solution

1. Step 1: Understand problem constraints

   The problem requires rearranging characters so no two adjacent are the same, which demands careful ordering based on frequency.

2. Step 2: Identify approach that guarantees optimality

   Greedy approach with a max heap always picks the most frequent character available that is not the previously used one, ensuring no adjacency violation and optimal placement.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max heap approach is standard and optimal for this problem [OK]

Hint: Max heap greedily picks highest frequency char [OK]

Common Mistakes:

• Assuming simple sorting suffices
• Thinking backtracking is efficient here
• Confusing DP with greedy

4. What is the time complexity of the optimal solution that sorts the list of numbers (converted to strings) using a custom comparator which compares concatenations of pairs?

medium

A. O(n * k * log n), where n is number of elements and k is max digit length

B. O(n! * n * k), where n is number of elements and k is max digit length

C. O(n^2 * k), where n is number of elements and k is max digit length

D. O(n log n * k), where n is number of elements and k is max digit length

Solution

1. Step 1: Identify sorting complexity

   Sorting n elements takes O(n log n) comparisons.

2. Step 2: Each comparison involves concatenating two strings of max length k and comparing them

   Each comparison is O(k), so total is O(n log n * k).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting with custom comparator comparing concatenations costs O(k) per comparison [OK]

Hint: Each comparison costs O(k), sorting O(n log n) times [OK]

Common Mistakes:

• Confusing O(n*k*log n) with O(n log n * k)
• Assuming O(n^2) due to pairwise comparisons
• Forgetting string concat cost

5. What is the time complexity of the optimal single-pass greedy solution for the Minimum Domino Rotations problem, given arrays of length n?

medium

A. O(6 * n) because it checks all numbers 1 to 6

B. O(n^2) due to nested loops over dominoes and candidates

C. O(n) because it only checks two candidate values with a single pass

D. O(1) since it only checks the first domino values

Solution

1. Step 1: Identify loops in the code

   The code checks at most two candidates (A[0] and B[0]) and iterates once over all n dominoes per candidate.

2. Step 2: Calculate total operations

   Each candidate check is O(n), so total is O(2 * n) = O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only two passes over n elements -> linear time [OK]

Hint: Only two candidates checked, linear scan each [OK]

Common Mistakes:

• Assuming all 6 numbers checked -> O(6n)
• Confusing nested loops causing O(n^2)