Description#
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] <= 108
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def minJumps(self, arr: List[int]) -> int:
idx = defaultdict(list)
for i, v in enumerate(arr):
idx[v].append(i)
q = deque([(0, 0)])
vis = {0}
while q:
i, step = q.popleft()
if i == len(arr) - 1:
return step
v = arr[i]
step += 1
for j in idx[v]:
if j not in vis:
vis.add(j)
q.append((j, step))
del idx[v]
if i + 1 < len(arr) and (i + 1) not in vis:
vis.add(i + 1)
q.append((i + 1, step))
if i - 1 >= 0 and (i - 1) not in vis:
vis.add(i - 1)
q.append((i - 1, step))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public int minJumps(int[] arr) {
Map<Integer, List<Integer>> idx = new HashMap<>();
int n = arr.length;
for (int i = 0; i < n; ++i) {
idx.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
Deque<int[]> q = new LinkedList<>();
Set<Integer> vis = new HashSet<>();
vis.add(0);
q.offer(new int[] {0, 0});
while (!q.isEmpty()) {
int[] e = q.pollFirst();
int i = e[0], step = e[1];
if (i == n - 1) {
return step;
}
int v = arr[i];
++step;
for (int j : idx.getOrDefault(v, new ArrayList<>())) {
if (!vis.contains(j)) {
vis.add(j);
q.offer(new int[] {j, step});
}
}
idx.remove(v);
if (i + 1 < n && !vis.contains(i + 1)) {
vis.add(i + 1);
q.offer(new int[] {i + 1, step});
}
if (i - 1 >= 0 && !vis.contains(i - 1)) {
vis.add(i - 1);
q.offer(new int[] {i - 1, step});
}
}
return -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
int minJumps(vector<int>& arr) {
unordered_map<int, vector<int>> idx;
int n = arr.size();
for (int i = 0; i < n; ++i) idx[arr[i]].push_back(i);
queue<pair<int, int>> q;
q.emplace(0, 0);
unordered_set<int> vis;
vis.insert(0);
while (!q.empty()) {
auto e = q.front();
q.pop();
int i = e.first, step = e.second;
if (i == n - 1) return step;
int v = arr[i];
++step;
if (idx.count(v)) {
for (int j : idx[v]) {
if (!vis.count(j)) {
vis.insert(j);
q.emplace(j, step);
}
}
idx.erase(v);
}
if (i + 1 < n && !vis.count(i + 1)) {
vis.insert(i + 1);
q.emplace(i + 1, step);
}
if (i - 1 >= 0 && !vis.count(i - 1)) {
vis.insert(i - 1);
q.emplace(i - 1, step);
}
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| func minJumps(arr []int) int {
idx := map[int][]int{}
for i, v := range arr {
idx[v] = append(idx[v], i)
}
vis := map[int]bool{0: true}
type pair struct{ idx, step int }
q := []pair{{0, 0}}
for len(q) > 0 {
e := q[0]
q = q[1:]
i, step := e.idx, e.step
if i == len(arr)-1 {
return step
}
step++
for _, j := range idx[arr[i]] {
if !vis[j] {
vis[j] = true
q = append(q, pair{j, step})
}
}
delete(idx, arr[i])
if i+1 < len(arr) && !vis[i+1] {
vis[i+1] = true
q = append(q, pair{i + 1, step})
}
if i-1 >= 0 && !vis[i-1] {
vis[i-1] = true
q = append(q, pair{i - 1, step})
}
}
return -1
}
|
