Sponsored
Sponsored
In this approach, we use a Breadth-First Search (BFS) to find the minimum number of jumps required. We start from the first index and explore all possible indices we can jump to. We maintain a queue that helps us process nodes level by level, where each level represents a jump.
We use a map to track all indices with the same value to make efficient jumps to similar value indices. Once an index is processed, we clear it from our map entries to avoid unnecessary recalculation.
Time Complexity: O(n), where n is the length of the array. The worst-case scenario processes every element once.
Space Complexity: O(n), due to additional storage for graph mapping and visited set.
1from collections import defaultdict, deque
2
3def min_jumps(arr):
4 if len(arr) == 1:
5 return 0
6
7 n = len(arr)
8 graph = defaultdict(list)
9 for i, num in enumerate(arr):
10 graph[num].append(i)
11
12 queue = deque([0])
13 visited = {0}
14 steps = 0
15
16 while queue:
17 steps += 1
18 for _ in range(len(queue)):
19 i = queue.popleft()
20 for j in graph[arr[i]]:
21 if j == n - 1:
22 return steps
23 if j not in visited:
24 visited.add(j)
25 queue.append(j)
26
27 graph[arr[i]].clear() # Optimization: Clear list to prevent redundant operations
28 for j in [i - 1, i + 1]:
29 if 0 <= j < n and j not in visited:
30 if j == n - 1:
31 return steps
32 visited.add(j)
33 queue.append(j)
34
35 return -1This Python solution uses BFS for level-order traversal. Each level in BFS corresponds to a jump. We utilize a deque for efficient pop from the queue and a set to track visited indices to avoid revisiting and redundant processing of indices. The defaultdict helps in storing and accessing indices sharing the same array values efficiently.
While the first BFS approach involved clearing the graph entry after processing, this approach incorporates an even lazier clearing technique. Instead of clearing as soon as we're done processing, we mark for future removal unless revisiting an edge is necessary. This maintains a balance between redundant work and excessive memory usage.
Time Complexity: O(n), because we explore each node a constant number of times.
Space Complexity: O(n), accommodating the graph structure and tracking nodes via additional containers.
1#include <vector>
2#include <unordered_map>
3#include <queue>
4
5using namespace std;
int minJumps(vector<int>& arr) {
if (arr.size() == 1) return 0;
unordered_map<int, vector<int>> graph;
for (int i = 0; i < arr.size(); i++) {
graph[arr[i]].push_back(i);
}
queue<int> q;
q.push(0);
vector<bool> visited(arr.size(), false);
visited[0] = true;
int steps = 0;
while (!q.empty()) {
steps++;
int size = q.size();
for (int i = 0; i < size; i++) {
int index = q.front();
q.pop();
for (int j : graph[arr[index]]) {
if (j == arr.size() - 1) return steps;
if (!visited[j]) {
visited[j] = true;
q.push(j);
}
}
graph[arr[index]].clear();
if (index - 1 >= 0 && !visited[index - 1]) {
visited[index - 1] = true;
q.push(index - 1);
}
if (index + 1 < arr.size() && !visited[index + 1]) {
visited[index + 1] = true;
q.push(index + 1);
}
}
}
return -1;
}The C++ solution leverages an unordered_map for organizing jumps and a queue to perform BFS similar to the Java approach. The difference lies in simplifying memory operations with lazy eviction of processed nodes to maintain simpler code and potentially decrease memory overhead.