source: https://leetcode.com/problems/jump-game-iv/description/
Jump Game IV
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
|
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
class Solution { public int minJumps(int[] arr) { Map<Integer, List<Integer>> map = new HashMap<>(); for(int i=0;i<arr.length;i++){ map.computeIfAbsent(arr[i], f -> new ArrayList<>()).add(i); } return bfs(arr, map, 0, arr.length-1); } private int bfs(int[] arr, Map<Integer, List<Integer>> map, int start, int dest){ Queue<Integer> next = new ArrayDeque<>(); boolean[] seen = new boolean[arr.length]; next.add(start); seen[start] = true; int level = 0; while(!next.isEmpty()){ int size = next.size(); for(int i=0;i<size;i++){ int n = next.poll(); if(n==dest) return level; for(int c: map.get(arr[n])){ if(!seen[c]){ seen[c] = true; next.add(c); } } //clear the list to prevent redundant search (without this you will get TLE) map.get(arr[n]).clear(); if(isValid(arr, n+1, seen)){ seen[n+1] = true; next.add(n+1); } if(isValid(arr, n-1, seen)){ seen[n-1] = true; next.add(n-1); } } level++; } return -1; } private boolean isValid(int[] arr, int i, boolean[] seen){ return i>=0 && i < arr.length && !seen[i]; } } |