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.
1import java.util.*;
2
3public class JumpGame {
4 public int minJumps(int[] arr) {
5 if (arr.length == 1) return 0;
6 Map<Integer, List<Integer>> graph = new HashMap<>();
7 for (int i = 0; i < arr.length; i++) {
8 graph.computeIfAbsent(arr[i], x -> new LinkedList<>()).add(i);
9 }
10 Queue<Integer> queue = new LinkedList<>();
11 queue.offer(0);
12 Set<Integer> visited = new HashSet<>();
13 visited.add(0);
14 int steps = 0;
15 while (!queue.isEmpty()) {
16 steps++;
17 int size = queue.size();
18 for (int i = 0; i < size; i++) {
19 int index = queue.poll();
20 for (int j : graph.get(arr[index])) {
21 if (j == arr.length - 1) return steps;
22 if (!visited.contains(j)) {
23 visited.add(j);
24 queue.offer(j);
25 }
26 }
27 graph.get(arr[index]).clear(); // Clear to prevent unnecessary checks
28 if (index - 1 >= 0 && visited.add(index - 1)) queue.offer(index - 1);
29 if (index + 1 < arr.length && visited.add(index + 1)) queue.offer(index + 1);
30 }
31 }
32 return -1;
33 }
34}The Java solution follows the BFS approach similar to the Python one, where we maintain a map (using HashMap) for the array indices associated with each unique number. We use a Queue to perform standard level-order BFS, and a HashSet for tracking visited nodes 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.