Given an array of integers arr, you are initially positioned at the first index of the array.
In one step you can jump from index i to index:
i + 1 where: i + 1 < arr.length.i - 1 where: i - 1 >= 0.j where: arr[i] == arr[j] and i != j.Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
Example 1:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404] Output: 3 Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
Example 2:
Input: arr = [7] Output: 0 Explanation: Start index is the last index. You do not need to jump.
Example 3:
Input: arr = [7,6,9,6,9,6,9,7] Output: 1 Explanation: You can jump directly from index 0 to index 7 which is last index of the array.
Constraints:
1 <= arr.length <= 5 * 104-108 <= arr[i] <= 108class Solution {
public:
int minJumps(vector<int>& arr) {
int n = arr.size();
unordered_map<int, vector<int>> indicesOfValue;
for (int i = 0; i < n; i++)
indicesOfValue[arr[i]].push_back(i);
vector<bool> visited(n); visited[0] = true;
queue<int> q; q.push(0);
int step = 0;
while (!q.empty()) {
for (int size = q.size(); size > 0; --size) {
int i = q.front(); q.pop();
if (i == n - 1) return step; // Reached to last index
vector<int>& next = indicesOfValue[arr[i]];
next.push_back(i - 1); next.push_back(i + 1);
for (int j : next) {
if (j >= 0 && j < n && !visited[j]) {
visited[j] = true;
q.push(j);
}
}
next.clear(); // avoid later lookup indicesOfValue arr[i]
}
step++;
}
return 0;
}
};class Solution {
public int minJumps(int[] arr) {
int n = arr.length, ans = 0;
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++)
graph.computeIfAbsent(arr[i], v -> new ArrayList<>()).add(i);
boolean[] vis = new boolean[n];
Queue<Integer> level = new LinkedList<>(Arrays.asList(0));
while (!level.isEmpty()) {
int size = level.size();
while (size-- > 0) {
int node = level.poll();
if (node == n - 1)
return ans;
// Check same valued jumps
for (int nbr : graph.get(arr[node])) {
if (!vis[nbr]) {
level.offer(nbr);
vis[nbr] = true;
}
}
graph.get(arr[node]).clear();
// Check adjacent jumps
if (0 < node && !vis[node - 1]) {
level.offer(node - 1);
vis[node - 1] = true;
}
if (node < n - 1 && !vis[node + 1]) {
level.offer(node + 1);
vis[node + 1] = true;
}
}
ans++;
}
return -1;
}
}class Solution {
public static int minJumps(int[] arr) {
int n = arr.length;
if (n <= 1) {
return 0;
}
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.computeIfAbsent(arr[i], v -> new LinkedList<>()).add(i);
}
HashSet<Integer> curs = new HashSet<>(); // store layers from start
curs.add(0);
Set<Integer> visited = new HashSet<>();
visited.add(0);
visited.add(n - 1);
int step = 0;
HashSet<Integer> other = new HashSet<>(); // store layers from end
other.add(n - 1);
// when current layer exists
while (!curs.isEmpty()) {
// search from the side with fewer nodes
if (curs.size() > other.size()) {
HashSet<Integer> tmp = curs;
curs = other;
other = tmp;
}
HashSet<Integer> nex = new HashSet<>();
// iterate the layer
for (int node : curs) {
// check same value
for (int child : graph.get(arr[node])) {
if (other.contains(child)) {
return step + 1;
}
if (!visited.contains(child)) {
visited.add(child);
nex.add(child);
}
}
// clear the list to prevent redundant search
graph.get(arr[node]).clear();
// check neighbors
if (other.contains(node + 1) || other.contains(node - 1)) {
return step + 1;
}
if (node + 1 < n && !visited.contains(node + 1)) {
visited.add(node + 1);
nex.add(node + 1);
}
if (node - 1 >= 0 && !visited.contains(node - 1)) {
visited.add(node - 1);
nex.add(node - 1);
}
}
curs = nex;
step++;
}
return -1;
}
}class Solution {
public static int minJumps(int[] arr) {
int n = arr.length;
if (n <= 1) {
return 0;
}
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.computeIfAbsent(arr[i], v -> new LinkedList<>()).add(i);
}
HashSet<Integer> curs = new HashSet<>(); // store layers from start
curs.add(0);
Set<Integer> visited = new HashSet<>();
visited.add(0);
visited.add(n - 1);
int step = 0;
HashSet<Integer> other = new HashSet<>(); // store layers from end
other.add(n - 1);
// when current layer exists
while (!curs.isEmpty()) {
// search from the side with fewer nodes
if (curs.size() > other.size()) {
HashSet<Integer> tmp = curs;
curs = other;
other = tmp;
}
HashSet<Integer> nex = new HashSet<>();
// iterate the layer
for (int node : curs) {
// check same value
for (int child : graph.get(arr[node])) {
if (other.contains(child)) {
return step + 1;
}
if (!visited.contains(child)) {
visited.add(child);
nex.add(child);
}
}
// clear the list to prevent redundant search
graph.get(arr[node]).clear();
// check neighbors
if (other.contains(node + 1) || other.contains(node - 1)) {
return step + 1;
}
if (node + 1 < n && !visited.contains(node + 1)) {
visited.add(node + 1);
nex.add(node + 1);
}
if (node - 1 >= 0 && !visited.contains(node - 1)) {
visited.add(node - 1);
nex.add(node - 1);
}
}
curs = nex;
step++;
}
return -1;
}
}