Solution: Jump Game III

We use cookies to provide you with an optimal experience and relevant communication.Cookie Policy

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Jump Game III

Table of Contents

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Problem Statement

You are given an array of non-negative integers arr and an initial position start. Starting at start, you can jump either arr[start] steps to the right or arr[start] steps to the left.

Return true if you can reach any index in the array that contains the value 0. Otherwise, return false.

Note that you cannot jump outside the bounds of the array.

Examples

Example 1:

Input: arr: [2, 2, 0, 3, 4], start: 1
Output: true
Justification: Starting from index 1, jump to index 3, then jump to index 0, and then jump to index 2, which contains 0.

Example 2:

Input: arr: [4, 1, 2, 3, 1, 0], start: 4
Output: true
Justification: Starting from index 4, jump to index 5, which contains 0.

Example 3:

Input: arr: [2, 3, 1, 1, 4], start: 0
Output: false
Justification: Starting from index 0, it is not possible to reach any index containing 0.

Constraints:

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

Solution

To solve this problem, we'll use a breadth-first search (BFS) approach. BFS is ideal for this problem because it explores all possible paths from the starting point in a layer-by-layer manner. This helps in finding the shortest path to any index with value 0, if such a path exists. The BFS approach uses a queue to keep track of indices to visit and a set to record visited indices, ensuring we do not reprocess the same index multiple times.

The BFS approach works well here because it ensures that we explore all possible jumps systematically. By visiting each possible jump from the current position, we can efficiently determine whether it is possible to reach an index containing 0.

Step-by-Step Algorithm

Initialization:
- Create a queue and initialize it with the start index.
- Create a map to keep track of visited indices.
- Mark the start index as visited.
BFS Loop:
- While the queue is not empty:
  - Dequeue the front element (current index).
  - If the value at the current index is 0, return true.
  - Calculate the possible next positions to jump to (both left and right).
  - For each next position:
    - If it is within bounds and not visited:
      - Enqueue the next position.
      - Mark the next position as visited.
Return:
- If the queue is empty and no index with value 0 is found, return false.

Algorithm Walkthrough

For the input arr: [2, 2, 0, 3, 4] and start: 1, let's go through the algorithm step-by-step:

Initialization:
- Queue: [1]
- Visited: {1}
BFS Loop:
- Dequeue: 1
  - Current value: 2
  - Possible next positions: 1 + 2 = 3, 1 - 2 = -1
  - Next valid positions to visit: 3
  - Enqueue: [3]
  - Visited: {1, 3}
- Dequeue: 3
  - Current value: 3
  - Possible next positions: 3 + 3 = 6, 3 - 3 = 0
  - Next valid positions to visit: 0
  - Enqueue: [0]
  - Visited: {0, 1, 3}
- Dequeue: 0
  - Current value: 2
  - Possible next positions: 0 + 2 = 2, 0 - 2 = -2
  - Next valid positions to visit: 2
  - Enqueue: [2]
  - Visited: {0, 1, 2, 3}
- Dequeue: 2
  - Current value: 0
  - The value is 0, so return true.

Code

Python3

. . . .

Complexity Analysis

Time Complexity: The time complexity of this algorithm is , where n is the number of elements in the array. This is because each index is visited at most once, and each element is processed at most twice (once for each possible jump).
Space Complexity: The space complexity is also due to the space required for the queue and the set used to keep track of visited indices. The queue and the set together can contain up to n elements in the worst case.

Mark as Completed

Table of Contents

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis