Jobs

Interviews

Discussions

Jump Game

Medium

Verily

3 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁵

Jump Game

Medium

Verily

3 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁵

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:

Can the array `nums` contain zero values, and if so, how should I handle them?
What is the maximum size of the `nums` array? Is it possible to have a very large array that could impact memory or time complexity?
Are all elements in the array non-negative integers, as stated in the problem description?
If it's impossible to reach the last index, should I return `false` or is there any other specific value expected in that scenario?
Is it always guaranteed that the array will contain at least one element?

Brute Force Solution

Approach

The brute force strategy for this game involves trying every possible path you could take. We essentially explore all possible jump sequences, even if they seem silly, until we find one that works.

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

Start at the beginning.
From where you are, consider all the possible jump distances you could make according to the number you see at your current position.
For each of those jump distances, pretend you actually made that jump and see where you land.
From that new landing spot, again, consider all the possible jump distances from *that* spot and where they would take you.
Continue this process, exploring every single possible jump you could make at each location.
If, at any point, one of these sequences of jumps gets you to the very end, you've found a winning path, and you know you can reach the end.
If you try every single combination of jumps and none of them get you to the end, then you can't reach the end.

Code Implementation

def can_jump_brute_force(jump_lengths):
    def solve(current_position):
        # If we've reached the end, we're done
        if current_position >= len(jump_lengths) - 1:
            return True

        maximum_jump = jump_lengths[current_position]

        # Iterate through all possible jump lengths
        for jump_length in range(1, maximum_jump + 1):
            next_position = current_position + jump_length

            # Explore the result of taking this jump
            if solve(next_position):
                return True

        # We've explored all jumps from here, and none work
        return False

    # Start from the beginning
    return solve(0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible jump sequences. At each index i, we can potentially make jumps of length 1, 2, up to nums[i]. In the worst-case scenario, for many indices, nums[i] will be large, leading to multiple branching possibilities. This branching exploration of possible jump combinations resembles a tree where each node can have multiple children. Thus, the number of paths explored grows exponentially with the input size n, resulting in a time complexity of O(2^n).

Space Complexity

O(N) – The described brute force approach explores all possible jump sequences using recursion. In the worst-case scenario, the recursion depth can reach N, where N is the number of elements in the input array. Each recursive call requires a new stack frame to store the current index and other function-related data. Thus, the maximum space used by the call stack is proportional to the input size N, leading to a space complexity of O(N).

Optimal Solution

Approach

The problem asks if you can reach the end, given you can jump a certain distance from each position. Instead of trying to jump every possible distance at each spot, the efficient approach determines how far you *need* to jump to reach the end.

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

Start at the very end of the line; this is your initial destination.
Move backward from the second-to-last spot.
For each spot, ask yourself: can I jump from here and reach my current destination?
If you can, then *this* spot becomes your new destination.
If you cannot reach your current destination, then do nothing, and just move back one more spot.
Keep moving backward until you reach the beginning.
If, after checking every spot, your destination is now the beginning of the line, then you know you can reach the end.
Otherwise, you can't.

Code Implementation

def can_jump_to_end(jump_lengths):
    destination_index = len(jump_lengths) - 1

    for i in range(len(jump_lengths) - 2, -1, -1):

        # Check if we can reach the current destination from this position
        if i + jump_lengths[i] >= destination_index:

            #If we can, update the destination to the current position.
            destination_index = i

    #If first position is the destination, we can reach the end.
    if destination_index == 0:
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates backward through the input array nums of size n, starting from the second-to-last element. For each element, it performs a constant-time check to see if it can reach the current destination. This check involves a single comparison: if nums[i] + i >= destination. The loop iterates n-1 times in the worst case, and each iteration involves a constant amount of work. Therefore, the total time complexity is O(n).

Space Complexity

O(1) – The provided algorithm iterates backward through the input array, maintaining a single variable to track the current 'destination' index. No additional data structures, such as lists, hash maps, or recursion stacks, are used to store intermediate results or track visited elements. Therefore, the amount of auxiliary space remains constant regardless of the input array's size (N), resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return true if the input is null or empty because an empty array trivially allows reaching the end (which is the start).
Single element array	Return true as a single-element array always allows reaching the end.
Array where the first element is zero	If the first element is zero and the array has more than one element, return false immediately because we cannot move from the starting position.
Array where all elements are zero (except perhaps the last)	Iterate to see if any position can reach beyond it's index, return false if we get stuck.
Array where early elements have large jump values, but later elements are mostly zeros	The algorithm needs to correctly handle scenarios where the large jumps are wasted if the later jumps cannot sustain the progress.
Array with a very long sequence of zeros preventing forward progress	The solution should be able to identify a sequence of zeros that prevents reaching the end, resulting in returning false.
Integer overflow if indices are large or number of jumps is large	The algorithm shouldn't perform computations with indices which could cause int overflow.
Large array size impacting performance	The algorithm should scale linearly O(n) with array size and should avoid recursive implementations that cause a stack overflow.

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:

Can the array `nums` contain zero values, and if so, how should I handle them?
What is the maximum size of the `nums` array? Is it possible to have a very large array that could impact memory or time complexity?
Are all elements in the array non-negative integers, as stated in the problem description?
If it's impossible to reach the last index, should I return `false` or is there any other specific value expected in that scenario?
Is it always guaranteed that the array will contain at least one element?

Brute Force Solution

Approach

The brute force strategy for this game involves trying every possible path you could take. We essentially explore all possible jump sequences, even if they seem silly, until we find one that works.

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

Start at the beginning.
From where you are, consider all the possible jump distances you could make according to the number you see at your current position.
For each of those jump distances, pretend you actually made that jump and see where you land.
From that new landing spot, again, consider all the possible jump distances from *that* spot and where they would take you.
Continue this process, exploring every single possible jump you could make at each location.
If, at any point, one of these sequences of jumps gets you to the very end, you've found a winning path, and you know you can reach the end.
If you try every single combination of jumps and none of them get you to the end, then you can't reach the end.

Code Implementation

def can_jump_brute_force(jump_lengths):
    def solve(current_position):
        # If we've reached the end, we're done
        if current_position >= len(jump_lengths) - 1:
            return True

        maximum_jump = jump_lengths[current_position]

        # Iterate through all possible jump lengths
        for jump_length in range(1, maximum_jump + 1):
            next_position = current_position + jump_length

            # Explore the result of taking this jump
            if solve(next_position):
                return True

        # We've explored all jumps from here, and none work
        return False

    # Start from the beginning
    return solve(0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the very end of the line; this is your initial destination.
Move backward from the second-to-last spot.
For each spot, ask yourself: can I jump from here and reach my current destination?
If you can, then *this* spot becomes your new destination.
If you cannot reach your current destination, then do nothing, and just move back one more spot.
Keep moving backward until you reach the beginning.
If, after checking every spot, your destination is now the beginning of the line, then you know you can reach the end.
Otherwise, you can't.

Code Implementation

def can_jump_to_end(jump_lengths):
    destination_index = len(jump_lengths) - 1

    for i in range(len(jump_lengths) - 2, -1, -1):

        # Check if we can reach the current destination from this position
        if i + jump_lengths[i] >= destination_index:

            #If we can, update the destination to the current position.
            destination_index = i

    #If first position is the destination, we can reach the end.
    if destination_index == 0:
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return true if the input is null or empty because an empty array trivially allows reaching the end (which is the start).
Single element array	Return true as a single-element array always allows reaching the end.
Array where the first element is zero	If the first element is zero and the array has more than one element, return false immediately because we cannot move from the starting position.
Array where all elements are zero (except perhaps the last)	Iterate to see if any position can reach beyond it's index, return false if we get stuck.
Array where early elements have large jump values, but later elements are mostly zeros	The algorithm needs to correctly handle scenarios where the large jumps are wasted if the later jumps cannot sustain the progress.
Array with a very long sequence of zeros preventing forward progress	The solution should be able to identify a sequence of zeros that prevents reaching the end, resulting in returning false.
Integer overflow if indices are large or number of jumps is large	The algorithm shouldn't perform computations with indices which could cause int overflow.
Large array size impacting performance	The algorithm should scale linearly O(n) with array size and should avoid recursive implementations that cause a stack overflow.