S
S
Study Notes
Search…
1345.jump-game-iv

# Problem Description

1
Given an array of integers arr, you are initially positioned at the first index of the array.
2
3
In one step you can jump from index i to index:
4
5
- i + 1 where: i + 1 < arr.length.
6
- i - 1 where: i - 1 >= 0.
7
- j where: arr[i] == arr[j] and i != j.
8
Return the minimum number of steps to reach the last index of the array.
9
10
Notice that you can not jump outside of the array at any time.
11
12
13
Example 1:
14
15
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
16
Output: 3
17
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
18
19
Example 2:
20
21
Input: arr = [7]
22
Output: 0
23
Explanation: Start index is the last index. You don't need to jump.
24
25
Example 3:
26
27
Input: arr = [7,6,9,6,9,6,9,7]
28
Output: 1
29
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.
30
31
Example 4:
32
33
Input: arr = [6,1,9]
34
Output: 2
35
36
Example 5:
37
38
Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
39
Output: 3
40
41
42
Constraints:
43
44
- 1 <= arr.length <= 5 * 10^4
45
- -10^8 <= arr[i] <= 10^8
Copied!

# Solution

This problem can use BFS to check, check each level, if already found in last index, then return, after each level, jumps+1. here level means 3 possible options to jump. so that we can find the min jump steps.
ways to jump from index `i`: 1. i + 1, if i + 1 < len && `i + 1` index not visited before 2. `i - 1`, if `i - 1 >= 0` && `i - 1` index not visited before. 3. different indexes which has the same value as value in index `i`.
Idea is to using Map to store element and corresponding indexes as key, value pair.
Queue to store each level indexes can jumped into from index `i`:
• first check curr index `i == len - 1 (last index)`
• if yes, terminate process, return jumps.
• if not, continue
• add `i + 1` if meet requirement, and mark as visited.
• add `i - 1` if meet requirement, and mark as visited
• add `map.get(arr[i])` -- the list of indexes if meet requirement, and mark visited. since it is already visited all indexes, then remove current element from map to avoid unnecessary visit.
• after each level, jumps+1
For example:
Jump Game IV

## Complexity Analysis

• Time Complexity: `O(n)`
• Space Complexity: `O(n)`
`n - n is length of arr`

# Key Points

• Group each size k subarray.
• Calculate avg of subarray of size k, compare with threshold
• Count increase 1 if meet requirements

# Code

Java Code
1
class Solution {
2
public int minJumps(int[] arr) {
3
4
if (arr.length == 1) return 0;
5
int jumps = 0;
6
int len = arr.length;
7
// add all indexes for the same value into map, key as element, value is the list of indexes for the element
8
Map<Integer, List<Integer>> map = new HashMap<>();
9
for (int i = 0; i < len; i++) {
10
11
}
12
// queue to keep index
13
14
// start from index 0
15
queue.offer(0);
16
// using HashSet to store already visited index, avoid dup visit
17
Set<Integer> visited = new HashSet<>();
18
while (!queue.isEmpty()) {
19
int size = queue.size();
20
while (size-- > 0) {
21
int currIdx = queue.poll();
22
23
if (currIdx = len - 1) return jumps;
24
// check 3 options to jump
25
// 1) i + 1, if i + 1 not visited, add into visited, and add into queue
26
if (currIdx + 1 < len && visited.add(currIdx + 1)) {
27
queue.offer(currIdx + 1);
28
}
29
// 2) i - 1, if i - 1 not visited, add into visited and queue
30
if (currIdx - 1 >= 0 && visited.add(currIdx - 1)) {
31
queue.offer(currIdx - 1);
32
}
33
// 3) the same value with different indexes
34
if (map.containsKey(arr[currIdx])) {
35
for (int idx : map.get(arr[currIdx])) {
36
37
queue.offer(idx);
38
}
39
}
40
// already visited, remove from map to avoid dup visit
41
map.remove(arr[curr]);
42
}
43
}
44
// after checking 3 possible ways, jumps + 1
45
jumps++;
46
}
47
return -1;
48
}
49
}
Copied!