Jobs

Interviews

Discussions

Jump Game III

Medium

Asked by:

More companies

30 views

Topics:

ArraysGraphsRecursion

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

1 <= arr.length <= 5 * 10⁴
0 <= arr[i] < arr.length
0 <= start < arr.length

Try coding it in LeetCode

Jump Game III

Medium

Asked by:

30 views

Topics:

ArraysGraphsRecursion

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

1 <= arr.length <= 5 * 10⁴
0 <= arr[i] < arr.length
0 <= start < arr.length

Try coding it in LeetCode

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 are the constraints on the size of the array `arr`? What is the range of values within the array?
Can the starting index `start` be out of bounds? If so, how should I handle that?
Is it possible for the array `arr` to be null or empty?
If there are multiple indices with value 0 reachable from the start index, is it sufficient to return true once any of them is reached?
Is the graph implicitly described by the jump rules guaranteed to be acyclic? If not, should I handle the possibility of infinite loops?

Brute Force Solution

Approach

The basic idea is to explore every possible path we can take. We'll start at the beginning and see where we can jump, then from each of those places, see where we can jump next, and so on, until we find our target or run out of options.

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

Start at the initial position.
From that position, consider every possible jump you can make as indicated by the value at that position.
For each of those jumps, check if it leads you to the target position.
If a jump leads to the target position, you've found a solution!
If a jump doesn't lead to the target position, remember this new position and try all possible jumps from it, repeating the same process as before.
Keep doing this until you either find the target position or you've tried all possible jumps from all reachable positions.
If you explore all reachable positions and never find the target, then the target cannot be reached from the starting position.

Code Implementation

def jump_game_iii_brute_force(array, start_index):
    # Use a stack to keep track of the indices to visit.
    indices_to_visit = [start_index]

    while indices_to_visit:
        current_index = indices_to_visit.pop()

        if array[current_index] == 0:
            return True

        jump_distance = array[current_index]

        # Prevents infinite loops by marking index as visited implicitly
        array[current_index] = -array[current_index]

        forward_index = current_index + jump_distance
        backward_index = current_index - jump_distance

        # Check if the forward jump is valid.
        if 0 <= forward_index < len(array) and array[forward_index] >= 0:
            indices_to_visit.append(forward_index)

        # Check if the backward jump is valid.
        if 0 <= backward_index < len(array) and array[backward_index] >= 0:
            indices_to_visit.append(backward_index)

    # No path found to an index with value 0.
    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each index of the array at most once. The worst-case scenario involves exploring all reachable indices before finding the target or exhausting all possibilities. Since each index contributes a constant amount of work (checking the jump options and marking as visited), the time complexity is directly proportional to the number of elements, n, in the array. Therefore, the time complexity is O(n).

Space Complexity

O(N) – The algorithm explores all possible paths using a recursive approach. In the worst-case scenario, the recursion depth can reach N, where N is the length of the input array, if the starting position allows us to explore nearly every element. Each recursive call adds a new frame to the call stack, leading to an auxiliary space usage proportional to the depth of the recursion. Therefore, the space complexity is O(N) due to the recursion call stack.

Optimal Solution

Approach

The key is to explore the possible jumps strategically, marking locations we've already visited to avoid repeating work. We start at the given location and systematically check where we can jump, until we find a location that holds the magic number.

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

Begin your exploration from the specified starting location.
Check the number at your current location. If it's the number you're looking for, you've found your answer!
If the number isn't the one you're looking for, decide where you can jump to. You have two choices: jump forward or jump backward, according to the number at your current location.
Before you jump, make sure you haven't already visited the location you're about to jump to. If you have, that path won't lead to a solution, so ignore it.
Mark the location you're currently at as 'visited' so you don't come back here again.
Jump to the new location and repeat the process, checking the number and deciding where to jump next. If you find the number you're looking for, you have a solution.
If you reach a point where you can't jump anymore (either you're at the edge or you've already visited all possible locations), then there's no path from the start to the magic number

Code Implementation

def jump_game_iii(array, start_index):
    array_length = len(array)
    visited_indices = [False] * array_length

    def can_reach_zero(current_index):
        # Check if the index is out of bounds.
        if current_index < 0 or current_index >= array_length:
            return False

        # Base case: we found the target value (0).
        if array[current_index] == 0:
            return True

        # If we've visited this index, avoid infinite loops.
        if visited_indices[current_index]:
            return False

        # Mark the current index as visited.
        visited_indices[current_index] = True

        jump_distance = array[current_index]
        # Explore both possible jump directions.
        return can_reach_zero(current_index + jump_distance) or \
               can_reach_zero(current_index - jump_distance)

    return can_reach_zero(start_index)

Big(O) Analysis

Time Complexity

O(n) – The algorithm explores the array by jumping forward or backward based on the value at each index. In the worst-case scenario, it might visit each of the n indices in the array. The visited array ensures each index is processed at most once, preventing infinite loops. Therefore, the time complexity is directly proportional to the number of elements in the array, resulting in O(n).

Space Complexity

O(N) – The algorithm uses a 'visited' marker for each location in the array to avoid revisiting. This 'visited' information effectively acts as an auxiliary boolean array. The size of this auxiliary array scales linearly with the size of the input array, which we can denote as N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately as there are no indices to explore.
Single element array where the element is 0 and start index is 0	Return true as the goal is already reached at the start.
Single element array where the element is not 0, regardless of start index	Return false as reaching 0 is impossible.
Start index is out of bounds	Return false if start index is invalid (less than 0 or greater than or equal to array length).
Array contains cycles (e.g., jumping back and forth between two indices)	Use a visited array/set to prevent infinite loops by marking visited indices.
No index with value 0 exists in the array, but a valid path exists without landing on 0.	The algorithm should still terminate and return false when all reachable nodes have been explored without finding a 0.
Large array size to test for stack overflow with recursive solutions.	Prefer an iterative solution (e.g., BFS) to avoid potential stack overflow errors.
Array with extreme jump lengths potentially leading to integer overflow when calculating new indices.	Ensure index calculations (i + arr[i], i - arr[i]) do not overflow, potentially using long data types or checking for overflow before performing jumps.

Null or empty input array

How to Handle:

Return false immediately as there are no indices to explore.

Single element array where the element is 0 and start index is 0

How to Handle:

Return true as the goal is already reached at the start.

Single element array where the element is not 0, regardless of start index

How to Handle:

Return false as reaching 0 is impossible.

Start index is out of bounds

How to Handle:

Return false if start index is invalid (less than 0 or greater than or equal to array length).

Array contains cycles (e.g., jumping back and forth between two indices)

How to Handle:

Use a visited array/set to prevent infinite loops by marking visited indices.

No index with value 0 exists in the array, but a valid path exists without landing on 0.

How to Handle:

The algorithm should still terminate and return false when all reachable nodes have been explored without finding a 0.

Large array size to test for stack overflow with recursive solutions.

How to Handle:

Prefer an iterative solution (e.g., BFS) to avoid potential stack overflow errors.

Array with extreme jump lengths potentially leading to integer overflow when calculating new indices.

How to Handle:

Ensure index calculations (i + arr[i], i - arr[i]) do not overflow, potentially using long data types or checking for overflow before performing jumps.

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 are the constraints on the size of the array `arr`? What is the range of values within the array?
Can the starting index `start` be out of bounds? If so, how should I handle that?
Is it possible for the array `arr` to be null or empty?
If there are multiple indices with value 0 reachable from the start index, is it sufficient to return true once any of them is reached?
Is the graph implicitly described by the jump rules guaranteed to be acyclic? If not, should I handle the possibility of infinite loops?

Brute Force Solution

Approach

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

Start at the initial position.
From that position, consider every possible jump you can make as indicated by the value at that position.
For each of those jumps, check if it leads you to the target position.
If a jump leads to the target position, you've found a solution!
If a jump doesn't lead to the target position, remember this new position and try all possible jumps from it, repeating the same process as before.
Keep doing this until you either find the target position or you've tried all possible jumps from all reachable positions.
If you explore all reachable positions and never find the target, then the target cannot be reached from the starting position.

Code Implementation

def jump_game_iii_brute_force(array, start_index):
    # Use a stack to keep track of the indices to visit.
    indices_to_visit = [start_index]

    while indices_to_visit:
        current_index = indices_to_visit.pop()

        if array[current_index] == 0:
            return True

        jump_distance = array[current_index]

        # Prevents infinite loops by marking index as visited implicitly
        array[current_index] = -array[current_index]

        forward_index = current_index + jump_distance
        backward_index = current_index - jump_distance

        # Check if the forward jump is valid.
        if 0 <= forward_index < len(array) and array[forward_index] >= 0:
            indices_to_visit.append(forward_index)

        # Check if the backward jump is valid.
        if 0 <= backward_index < len(array) and array[backward_index] >= 0:
            indices_to_visit.append(backward_index)

    # No path found to an index with value 0.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Begin your exploration from the specified starting location.
Check the number at your current location. If it's the number you're looking for, you've found your answer!
If the number isn't the one you're looking for, decide where you can jump to. You have two choices: jump forward or jump backward, according to the number at your current location.
Before you jump, make sure you haven't already visited the location you're about to jump to. If you have, that path won't lead to a solution, so ignore it.
Mark the location you're currently at as 'visited' so you don't come back here again.
Jump to the new location and repeat the process, checking the number and deciding where to jump next. If you find the number you're looking for, you have a solution.
If you reach a point where you can't jump anymore (either you're at the edge or you've already visited all possible locations), then there's no path from the start to the magic number

Code Implementation

def jump_game_iii(array, start_index):
    array_length = len(array)
    visited_indices = [False] * array_length

    def can_reach_zero(current_index):
        # Check if the index is out of bounds.
        if current_index < 0 or current_index >= array_length:
            return False

        # Base case: we found the target value (0).
        if array[current_index] == 0:
            return True

        # If we've visited this index, avoid infinite loops.
        if visited_indices[current_index]:
            return False

        # Mark the current index as visited.
        visited_indices[current_index] = True

        jump_distance = array[current_index]
        # Explore both possible jump directions.
        return can_reach_zero(current_index + jump_distance) or \
               can_reach_zero(current_index - jump_distance)

    return can_reach_zero(start_index)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately as there are no indices to explore.
Single element array where the element is 0 and start index is 0	Return true as the goal is already reached at the start.
Single element array where the element is not 0, regardless of start index	Return false as reaching 0 is impossible.
Start index is out of bounds	Return false if start index is invalid (less than 0 or greater than or equal to array length).
Array contains cycles (e.g., jumping back and forth between two indices)	Use a visited array/set to prevent infinite loops by marking visited indices.
No index with value 0 exists in the array, but a valid path exists without landing on 0.	The algorithm should still terminate and return false when all reachable nodes have been explored without finding a 0.
Large array size to test for stack overflow with recursive solutions.	Prefer an iterative solution (e.g., BFS) to avoid potential stack overflow errors.
Array with extreme jump lengths potentially leading to integer overflow when calculating new indices.	Ensure index calculations (i + arr[i], i - arr[i]) do not overflow, potentially using long data types or checking for overflow before performing jumps.

Null or empty input array

How to Handle:

Return false immediately as there are no indices to explore.

Single element array where the element is 0 and start index is 0

How to Handle:

Return true as the goal is already reached at the start.

Single element array where the element is not 0, regardless of start index

How to Handle:

Return false as reaching 0 is impossible.

Start index is out of bounds

How to Handle:

Return false if start index is invalid (less than 0 or greater than or equal to array length).

Array contains cycles (e.g., jumping back and forth between two indices)

How to Handle:

Use a visited array/set to prevent infinite loops by marking visited indices.

No index with value 0 exists in the array, but a valid path exists without landing on 0.

How to Handle:

The algorithm should still terminate and return false when all reachable nodes have been explored without finding a 0.

Large array size to test for stack overflow with recursive solutions.

How to Handle:

Prefer an iterative solution (e.g., BFS) to avoid potential stack overflow errors.

Array with extreme jump lengths potentially leading to integer overflow when calculating new indices.

How to Handle:

Ensure index calculations (i + arr[i], i - arr[i]) do not overflow, potentially using long data types or checking for overflow before performing jumps.