Jobs

Interviews

Discussions

Jump Game II

Medium

Asked by:

+16

26 views

Topics:

ArraysGreedy Algorithms

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 1000
It's guaranteed that you can reach nums[n - 1].

Jump Game II

Medium

Asked by:

+10

26 views

Topics:

ArraysGreedy Algorithms

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 1000
It's guaranteed that you can reach nums[n - 1].

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array nums?
Is it guaranteed that I can always reach the last index?
Are all elements in the nums array non-negative integers?
If nums has only one element, what should be the return value?
What should I return if it's impossible to reach the last index?

Brute Force Solution

Approach

The goal is to find the fewest jumps needed to reach the end. The brute force method tries every single possible path of jumps, exploring all combinations to see which one reaches the end with the smallest number of jumps.

Here's how the algorithm would work step-by-step:

Start at the beginning.
Look at all possible jump lengths you can make from the current spot.
For each of those jump lengths, imagine taking that jump and see where you land.
From each of those new spots, again look at all possible jump lengths you can now make.
Keep going, exploring all possible jump combinations from each spot, until you either reach the end or you can't jump any further.
If you reach the end, remember how many jumps it took to get there.
Do this for every single possible jump path from the starting point.
After exploring every possibility, compare all the paths that reached the end, and pick the one that used the fewest jumps.

Code Implementation

def jump_game_brute_force(numbers):
    if not numbers:
        return 0

    number_of_jumps = float('inf')

    def solve_jump_game(current_index, jumps_taken):
        nonlocal number_of_jumps

        # Found a path to the end, record jumps
        if current_index >= len(numbers) - 1:
            number_of_jumps = min(number_of_jumps, jumps_taken)
            return

        maximum_reach = numbers[current_index]

        # If we can't jump, this path is invalid
        if maximum_reach == 0:
            return

        # Iterate through all possible jump lengths
        for jump_length in range(1, maximum_reach + 1):
            next_index = current_index + jump_length
            solve_jump_game(next_index, jumps_taken + 1)

    # Start exploring from the begining
    solve_jump_game(0, 0)

    if number_of_jumps == float('inf'):
        return -1
    else:
        return number_of_jumps

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The described brute force approach explores every possible jump combination. In the worst case, from each position, we might be able to jump to almost every subsequent position. This creates a branching factor close to n at each step. Since there are n positions, the total number of possible jump paths grows exponentially, leading to approximately O(n^n) which is simplified by considering that there can only be jumps of maximum size to O(2^n).

Space Complexity

O(N^N) – The brute force approach described explores every possible jump combination using recursion. In the worst-case, at each index, we could potentially try every possible jump length from 1 up to the maximum jump value at that index. This leads to a branching factor that is at worst proportional to N at each of the N possible positions, resulting in a recursion tree that can grow exponentially. The maximum depth of the recursion tree can be N, and at each level, the number of branches is also proportional to N, meaning that there are potentially N^N branches or call stack frames being held at a time. Therefore, the space complexity for the call stack becomes O(N^N).

Optimal Solution

Approach

The goal is to reach the end using the fewest jumps possible. We don't need to find every possible path; we just need to greedily select the jump that gets us furthest along at each step.

Here's how the algorithm would work step-by-step:

Think of the problem as finding the furthest point you can reach with each jump.
Start at the beginning. Find the maximum distance you can jump from this position.
Treat all the positions you can reach from this initial jump as a 'window'. Within that window, find the position that allows you to jump the furthest overall.
Make your next jump to that position you identified in the window.
Repeat the process: find the new window (the reachable positions from your current spot), select the position that allows you to jump the furthest, and jump there.
Keep doing this until you reach the end. The number of jumps you took is the answer.

Code Implementation

def jump_game_two(nums):
    array_length = len(nums)
    current_reach = 0
    next_reach = 0
    jumps = 0

    for i in range(array_length - 1):
        # Update how far we can reach
        next_reach = max(next_reach, i + nums[i])

        if i == current_reach:
            # Need to jump because we've reached the limit
            jumps += 1
            current_reach = next_reach

            # If we can't reach further, impossible to finish
            if current_reach <= i:
                return -1

    return jumps

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array once. In each iteration, it finds the furthest reachable position within the current 'window' of reachable positions. Although there might appear to be nested loops, each element in the array is visited at most twice (once as the current position and potentially once within the window search). Thus, the number of operations is directly proportional to the size of the input array (n). Therefore the time complexity simplifies to O(n).

Space Complexity

O(1) – The provided approach focuses on iteratively updating the current position and the furthest reachable point. It only uses a few integer variables to store indices, jump counts, current reachable range, and next reachable range. These variables consume a constant amount of extra memory regardless of the input array's size (N). Therefore, the algorithm's auxiliary space complexity is O(1), as the space usage does not scale with the input size.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the array is null or empty, as no jumps are needed.
Array with a single element	Return 0 if the array has only one element because you start at the first index.
First element is zero, and array length is greater than 1	Return -1 (or throw an exception) because it's impossible to move from the first position.
Array where it's impossible to reach the last index	Return -1 if the last index cannot be reached.
Array with all 1s	Handle correctly as each jump moves one step forward.
Large jump lengths that could potentially cause integer overflow in intermediate calculations.	Ensure intermediate calculations use appropriate data types to prevent integer overflow.
Very large input array size	The solution should be designed to scale well and avoid excessive memory usage for large inputs (e.g., O(n) space complexity).
Input array with very large numbers, close to integer max	The algorithm should handle large numbers without causing overflow issues in calculations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array nums?
Is it guaranteed that I can always reach the last index?
Are all elements in the nums array non-negative integers?
If nums has only one element, what should be the return value?
What should I return if it's impossible to reach the last index?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning.
Look at all possible jump lengths you can make from the current spot.
For each of those jump lengths, imagine taking that jump and see where you land.
From each of those new spots, again look at all possible jump lengths you can now make.
Keep going, exploring all possible jump combinations from each spot, until you either reach the end or you can't jump any further.
If you reach the end, remember how many jumps it took to get there.
Do this for every single possible jump path from the starting point.
After exploring every possibility, compare all the paths that reached the end, and pick the one that used the fewest jumps.

Code Implementation

def jump_game_brute_force(numbers):
    if not numbers:
        return 0

    number_of_jumps = float('inf')

    def solve_jump_game(current_index, jumps_taken):
        nonlocal number_of_jumps

        # Found a path to the end, record jumps
        if current_index >= len(numbers) - 1:
            number_of_jumps = min(number_of_jumps, jumps_taken)
            return

        maximum_reach = numbers[current_index]

        # If we can't jump, this path is invalid
        if maximum_reach == 0:
            return

        # Iterate through all possible jump lengths
        for jump_length in range(1, maximum_reach + 1):
            next_index = current_index + jump_length
            solve_jump_game(next_index, jumps_taken + 1)

    # Start exploring from the begining
    solve_jump_game(0, 0)

    if number_of_jumps == float('inf'):
        return -1
    else:
        return number_of_jumps

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to reach the end using the fewest jumps possible. We don't need to find every possible path; we just need to greedily select the jump that gets us furthest along at each step.

Here's how the algorithm would work step-by-step:

Think of the problem as finding the furthest point you can reach with each jump.
Start at the beginning. Find the maximum distance you can jump from this position.
Treat all the positions you can reach from this initial jump as a 'window'. Within that window, find the position that allows you to jump the furthest overall.
Make your next jump to that position you identified in the window.
Repeat the process: find the new window (the reachable positions from your current spot), select the position that allows you to jump the furthest, and jump there.
Keep doing this until you reach the end. The number of jumps you took is the answer.

Code Implementation

def jump_game_two(nums):
    array_length = len(nums)
    current_reach = 0
    next_reach = 0
    jumps = 0

    for i in range(array_length - 1):
        # Update how far we can reach
        next_reach = max(next_reach, i + nums[i])

        if i == current_reach:
            # Need to jump because we've reached the limit
            jumps += 1
            current_reach = next_reach

            # If we can't reach further, impossible to finish
            if current_reach <= i:
                return -1

    return jumps

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the array is null or empty, as no jumps are needed.
Array with a single element	Return 0 if the array has only one element because you start at the first index.
First element is zero, and array length is greater than 1	Return -1 (or throw an exception) because it's impossible to move from the first position.
Array where it's impossible to reach the last index	Return -1 if the last index cannot be reached.
Array with all 1s	Handle correctly as each jump moves one step forward.
Large jump lengths that could potentially cause integer overflow in intermediate calculations.	Ensure intermediate calculations use appropriate data types to prevent integer overflow.
Very large input array size	The solution should be designed to scale well and avoid excessive memory usage for large inputs (e.g., O(n) space complexity).
Input array with very large numbers, close to integer max	The algorithm should handle large numbers without causing overflow issues in calculations.