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.
Flowchart Walkthrough
Let's analyze LeetCode problem 1345. Jump Game IV using the algorithm flowchart. Here's a step-by-step walkthrough to deduce the appropriate algorithm:
Is it a graph?
- Yes: Although not explicitly structured as a graph, the connections dictated by the indices and values (i.e., jumps to indices of the same value, forward and backward by one) allow it to be represented as a graph.
Is it a tree?
- No: The graph isn't necessarily hierarchical, as it includes multiple pathways via index values to potentially re-visit nodes.
Is the problem related to directed acyclic graphs (DAGs)?
- No: This problem involves a general graph where cycles may exist due to the ability to jump backward and forward to elements with the same value.
Is the problem related to shortest paths?
- Yes: The objective is to find the minimum number of jumps to get from the start to the end of the array, which can be framed as finding the shortest path in a graph.
Is the graph weighted?
- No: Every jump, irrespective of its length (either index difference or value-based connectivity), is treated equally with a basic increment in count.
Conclusion: Following the flowchart, the emphasis on shortest paths in an unweighted setting suggests the application of the Breadth-First Search (BFS) pattern. BFS is ideal as it effectively explores each level or layer (i.e., connections or jumps that can be made in one move), ensuring the shortest path is found in an unweighted graph.
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.
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
): Adefaultdict
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 withdeque
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 wherearr[i] == arr[j]
are added to the queue, with the number of steps incremented by1
, 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
andi - 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))
- It dequeues an element, which is a tuple of the current index (
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 and0
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 index0
.vis = {0}
-
Begin the BFS Loop:
-
Dequeue
(0, 0)
. Current indexi = 0
, steps takenstep = 0
.- We found the value
100
at index0
. Indices with value100
are[0, 3, 5]
. - Queue up index
3
and5
withstep+1
since0
is already visited. - Update queue:
q = deque([(3, 1), (5, 1)])
andvis = {0, 3, 5}
. - Remove
100
from theidx
dictionary to prevent future jumps to these indices:del idx[100]
.
- We found the value
-
Dequeue
(3, 1)
. Current indexi = 3
, steps takenstep = 1
.- Value at index
3
is100
, but we've already deleted it fromidx
. - We check the neighbors, and
4
has not been visited, so we queue it up. - Update queue:
q = deque([(5, 1), (4, 2)])
andvis = {0, 3, 4, 5}
.
- Value at index
-
Dequeue
(5, 1)
. Current indexi = 5
, steps takenstep = 1
.- We've reached the last index of the array, so we return the number of steps:
1
.
- We've reached the last index of the array, so we return the number of steps:
-
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
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.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.