1345. Jump Game IV

Problem Description

The problem involves an array of integers arr and a character that starts at the first index of the array. This character can jump to a new index in one of three ways. They can jump to the next index (i + 1), jump back to the previous index (i - 1), or jump to any index j that contains the same value as the current index (arr[i] == arr[j] and i != j). The goal is to determine the minimum number of steps required to reach the last index of the array. It is important to note that jumps can only occur within the bounds of the array, meaning that the character cannot jump to an index outside of the array.

Intuition

To arrive at the solution, we use breadth-first search (BFS) as the main strategy since the goal is to find the minimum number of steps. BFS is suitable for this kind of problem because it explores the nearest neighbors first and only goes deeper once there are no more neighbors to explore. Given this approach, we start from the first index and explore all possible jumps. To avoid revisiting indices and getting stuck in loops, we use a visited set (vis) to keep track of which indices have already been explored. Also, to avoid repeatedly performing the same jumps, we use a dictionary (idx) that maps each value to its indices in the array.

As we progress, we store in a queue (q) each index we can jump to, along with the number of steps taken to reach there. Once the jump to the last index is made, we return the number of steps that led to it as the result. To make the BFS efficient, after checking all indices that have the same value as the current index, we delete the entry from the idx dictionary to prevent redundant jumps in the future. This speeds up the BFS process significantly, as it reduces the number of potential jumps that are not helpful in reaching the end of the array quickly.

Learn more about Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological SortUniform Cost SearchMonotonic StackMemoization

I don’t know

Solution Approach

To solve this problem, the code uses the Breadth-First Search (BFS) algorithm, which is a standard approach for finding the shortest path in an unweighted graph or the fewest number of steps to reach a certain point.

Here's a walkthrough of the implementation:

Index Dictionary (idx): A defaultdict from Python's collections module is used to create a dictionary where each value in the array is a key, and the corresponding value is a list of all indices in the array with that value.

1idx = defaultdict(list)
2for i, v in enumerate(arr):
3    idx[v].append(i)

Queue (q): A queue is implemented with deque from the collections module, and it's initialized with a tuple containing the starting index (0) and the initial step count (0).
```
1q = deque([(0, 0)])
```
Visited Set (vis): A set is used to keep track of the indices that have been visited. This prevents the algorithm from processing an index more than once and ensures not to get caught in an infinite loop.
```
1vis = {0}
```

BFS Loop: The algorithm processes the queue q until it's empty, doing the following:

It dequeues an element, which is a tuple of the current index (i) and the number of steps taken to reach this index (step).
If the dequeued index is the last index of the array, the number of steps is immediately returned.
All indices j in the array where arr[i] == arr[j] are added to the queue, with the number of steps incremented by 1, and marked as visited.
After processing all jumps to the same value, that value is deleted from idx to prevent future unnecessary jumps to those indices.
The algorithm then looks to add the neighbor indices i + 1 and i - 1 to the queue (if they haven't been visited yet).

1while q:
2    i, step = q.popleft()
3    if i == len(arr) - 1:
4        return step
5    v = arr[i]
6    step += 1
7    for j in idx[v]:
8        if j not in vis:
9            vis.add(j)
10            q.append((j, step))
11    del idx[v]
12    if i + 1 < len(arr) and (i + 1) not in vis:
13        vis.add(i + 1)
14        q.append((i + 1, step))
15    if i - 1 >= 0 and (i - 1) not in vis:
16        vis.add(i - 1)
17        q.append((i - 1, step))

By employing BFS, which explores all possible paths breadthwise and visits each node exactly once, the solution finds the minimum number of steps needed to reach the last index of the array.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Example Walkthrough

Let's walk through a small example to illustrate the solution approach for the array arr = [100, 23, 23, 100, 23, 100].

Initialize the Index Dictionary (idx): We create a dictionary mapping each value in the array to a list of all indices in the array with that value.
- idx[100] = [0, 3, 5]
- idx[23] = [1, 2, 4]
Initialize the Queue (q): We start with the first index and 0 steps as we haven't yet taken any steps.
- q = deque([(0, 0)])
Initialize the Visited Set (vis): To begin, we've only visited the start index 0.
- vis = {0}
Begin the BFS Loop:
- Dequeue (0, 0). Current index i = 0, steps taken step = 0.
  - We found the value 100 at index 0. Indices with value 100 are [0, 3, 5].
  - Queue up index 3 and 5 with step+1 since 0 is already visited.
  - Update queue: q = deque([(3, 1), (5, 1)]) and vis = {0, 3, 5}.
  - Remove 100 from the idx dictionary to prevent future jumps to these indices: del idx[100].
- Dequeue (3, 1). Current index i = 3, steps taken step = 1.
  - Value at index 3 is 100, but we've already deleted it from idx.
  - We check the neighbors, and 4 has not been visited, so we queue it up.
  - Update queue: q = deque([(5, 1), (4, 2)]) and vis = {0, 3, 4, 5}.
- Dequeue (5, 1). Current index i = 5, steps taken step = 1.
  - We've reached the last index of the array, so we return the number of steps: 1.

In this example, by using BFS and our optimizations, we've found that we can reach the end of the array arr in just 1 step through the value jumps. We can jump directly from the first index to the last index since they share the same value of 100.

Solution Implementation

1from collections import defaultdict, deque
2from typing import List
3
4class Solution:
5    def min_jumps(self, arr: List[int]) -> int:
6        # Initialize a dictionary to keep track of indices for each value in the array
7        index_map = defaultdict(list)
8        for index, value in enumerate(arr):
9            index_map[value].append(index)
10          
11        # Initialize a queue with a tuple containing the start index and initial step count
12        queue = deque([(0, 0)])
13      
14        # Set to keep track of visited nodes to avoid cycles
15        visited = set([0])
16
17        # Process the queue until empty
18        while queue:
19            position, step_count = queue.popleft()
20
21            # If the end of the array is reached, return the count of steps
22            if position == len(arr) - 1:
23                return step_count
24          
25            # Increment the count of steps for the next jump
26            step_count += 1
27          
28            # Jump to all indexes with the same value as the current position
29            value = arr[position]
30            for next_position in index_map[value]:
31                if next_position not in visited:
32                    visited.add(next_position)
33                    queue.append((next_position, step_count))
34          
35            # Since all jumps for this value are done, clear the index list to prevent future jumps to the same value
36            del index_map[value]
37          
38            # Add the next consecutive index to the queue if it hasn't been visited
39            if position + 1 < len(arr) and (position + 1) not in visited:
40                visited.add(position + 1)
41                queue.append((position + 1, step_count))
42          
43            # Add the previous index to the queue if it hasn't been visited and it's within bounds
44            if position - 1 >= 0 and (position - 1) not in visited:
45                visited.add(position - 1)
46                queue.append((position - 1, step_count))
47
48        return -1  # If end is not reached, return -1 (this part of code should not be reached).
49
50# Example usage:
51# sol = Solution()
52# print(sol.min_jumps([100, -23, -23, 404, 100, 23, 23, 23, 3, 404]))
53

1class Solution {
2  
3    // Finds minimum number of jumps to reach the end of the array.
4    public int minJumps(int[] arr) {
5        // Hash map to store indices of values in the array.
6        Map<Integer, List<Integer>> indexMap = new HashMap<>();
7        int n = arr.length;
8      
9        // Populate the hash map with indices for each value.
10        for (int i = 0; i < n; ++i) {
11            indexMap.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
12        }
13      
14        // Queue for BFS, each element is a pair: [current index, current step count].
15        Deque<int[]> queue = new LinkedList<>();
16        // Set to keep track of visited indices.
17        Set<Integer> visited = new HashSet<>();
18      
19        // Start BFS with the first index.
20        visited.add(0);
21        queue.offer(new int[] {0, 0});
22      
23        // BFS to find minimum steps.
24        while (!queue.isEmpty()) {
25            int[] element = queue.pollFirst();
26            int currentIndex = element[0], stepCount = element[1];
27          
28            // If we've reached the end of the array, return the step count.
29            if (currentIndex == n - 1) {
30                return stepCount;
31            }
32          
33            // Increment step count for next potential moves.
34            stepCount++;
35          
36            // Get all indices with the same value and add unseen ones to the queue.
37            for (int index : indexMap.getOrDefault(arr[currentIndex], new ArrayList<>())) {
38                if (!visited.contains(index)) {
39                    visited.add(index);
40                    queue.offer(new int[] {index, stepCount});
41                }
42            }
43          
44            // We remove this value from the map to prevent revisiting.
45            indexMap.remove(arr[currentIndex]);
46          
47            // Check and add unseen next and previous indices to the queue.
48            if (currentIndex + 1 < n && !visited.contains(currentIndex + 1)) {
49                visited.add(currentIndex + 1);
50                queue.offer(new int[] {currentIndex + 1, stepCount});
51            }
52            if (currentIndex - 1 >= 0 && !visited.contains(currentIndex - 1)) {
53                visited.add(currentIndex - 1);
54                queue.offer(new int[] {currentIndex - 1, stepCount});
55            }
56        }
57      
58        // If we've exhausted all options and haven't reached the end, return -1.
59        return -1;
60    }
61}
62

1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4#include <queue>
5
6class Solution {
7public:
8    // Function to find the minimum number of jumps required to reach 
9    // the last index of the array where each element indicates the maximum 
10    // length of jump we can make from that position.
11    int minJumps(std::vector<int>& arr) {
12        // Map to hold the indices for each value in arr.
13        std::unordered_map<int, std::vector<int>> indexMap;
14        int n = arr.size();
15
16        // Populate the index map with the indices for each value.
17        for (int i = 0; i < n; ++i) {
18            indexMap[arr[i]].push_back(i);
19        }
20
21        // Queue to perform BFS, holding pairs of the index in arr and the number of steps taken.
22        std::queue<std::pair<int, int>> bfsQueue;
23        bfsQueue.emplace(0, 0); // Start from the first element.
24
25        // Set to keep track of visited indices to avoid revisits.
26        std::unordered_set<int> visited;
27        visited.insert(0);
28
29        // Perform BFS.
30        while (!bfsQueue.empty()) {
31            auto current = bfsQueue.front();
32            bfsQueue.pop();
33            int currentIndex = current.first, steps = current.second;
34
35            // If we have reached the last index, return the number of steps.
36            if (currentIndex == n - 1) return steps;
37
38            // Number of steps to reach the next index.
39            ++steps;
40            int currentValue = arr[currentIndex];
41
42            // If we can jump to any index with the same value as currentValue.
43            if (indexMap.count(currentValue)) {
44                for (int nextIndex : indexMap[currentValue]) {
45                    if (!visited.count(nextIndex)) {
46                        visited.insert(nextIndex);
47                        bfsQueue.emplace(nextIndex, steps);
48                    }
49                }
50                // To avoid unnecessary iterations in the future, erase the value from the map.
51                indexMap.erase(currentValue);
52            }
53
54            // Check the possibilities of jumping to adjacent indices.
55            if (currentIndex + 1 < n && !visited.count(currentIndex + 1)) {
56                visited.insert(currentIndex + 1);
57                bfsQueue.emplace(currentIndex + 1, steps);
58            }
59            if (currentIndex - 1 >= 0 && !visited.count(currentIndex - 1)) {
60                visited.insert(currentIndex - 1);
61                bfsQueue.emplace(currentIndex - 1, steps);
62            }
63        }
64
65        return -1; // If it's not possible to reach the end, return -1.
66    }
67};
68

1type IndexStepsPair = { index: number; steps: number };
2
3function minJumps(arr: number[]): number {
4  // Map to hold the indices for each value in arr.
5  const indexMap: Record<number, number[]> = {};
6  const n: number = arr.length;
7
8  // Populate the index map with the indices for each value.
9  for (let i = 0; i < n; i++) {
10    if (!(arr[i] in indexMap)) {
11      indexMap[arr[i]] = [];
12    }
13    indexMap[arr[i]].push(i);
14  }
15
16  // Queue to perform BFS, holding pairs of the index in arr and the number of steps taken.
17  const bfsQueue: IndexStepsPair[] = [{ index: 0, steps: 0 }];
18
19  // Set to keep track of visited indices to avoid revisits.
20  const visited: Set<number> = new Set();
21  visited.add(0);
22
23  // Perform BFS.
24  while (bfsQueue.length > 0) {
25    const current = bfsQueue.shift()!; // Assumed to not be undefined
26    const currentIndex = current.index;
27    let steps = current.steps;
28
29    // If we have reached the last index, return the number of steps.
30    if (currentIndex === n - 1) {
31      return steps;
32    }
33
34    // Number of steps to reach the next index.
35    steps++;
36
37    if (indexMap[arr[currentIndex]]) {
38      for (const nextIndex of indexMap[arr[currentIndex]]) {
39        if (!visited.has(nextIndex)) {
40          visited.add(nextIndex);
41          bfsQueue.push({ index: nextIndex, steps: steps });
42        }
43      }
44      // To avoid unnecessary iterations in the future, delete the value from the map.
45      delete indexMap[arr[currentIndex]];
46    }
47
48    // Check the possibilities of jumping to adjacent indices.
49    if (currentIndex + 1 < n && !visited.has(currentIndex + 1)) {
50      visited.add(currentIndex + 1);
51      bfsQueue.push({ index: currentIndex + 1, steps: steps });
52    }
53    if (currentIndex - 1 >= 0 && !visited.has(currentIndex - 1)) {
54      visited.add(currentIndex - 1);
55      bfsQueue.push({ index: currentIndex - 1, steps: steps });
56    }
57  }
58
59  // If it's not possible to reach the end, return -1.
60  return -1;
61}
62

Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

I don’t know

Time and Space Complexity

The time complexity of the provided code is O(N + E) where N is the number of elements in arr and E is the total number of edges in the graph constructed where each value in arr has edges to indices with the same value. The while loop runs for each index in arr once, and each index is added to the queue at most once. The inner loops contribute to the edges. Deletion of keys in the idx dictionary ensures that each value's list is iterated over at most once, hence, contributing to E.

The space complexity is O(N) as we need to store the indices in the idx dictionary, which in the worst case will store all indices, and the vis set, which also could potentially store all indices if they are visited. The queue could also hold up to N-1 elements in the worst case scenario.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1345. Jump Game IV

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings