Breadth-First Search
Array
Hash Table
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
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution :
def minJumps ( self , arr : List [ int ]) -> int :
g = defaultdict ( list )
for i , x in enumerate ( arr ):
g [ x ] . append ( i )
q = deque ([ 0 ])
vis = { 0 }
ans = 0
while 1 :
for _ in range ( len ( q )):
i = q . popleft ()
if i == len ( arr ) - 1 :
return ans
for j in ( i + 1 , i - 1 , * g . pop ( arr [ i ], [])):
if 0 <= j < len ( arr ) and j not in vis :
q . append ( j )
vis . add ( j )
ans += 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 class Solution {
public int minJumps ( int [] arr ) {
Map < Integer , List < Integer >> g = new HashMap <> ();
int n = arr . length ;
for ( int i = 0 ; i < n ; i ++ ) {
g . computeIfAbsent ( arr [ i ] , k -> new ArrayList <> ()). add ( i );
}
boolean [] vis = new boolean [ n ] ;
Deque < Integer > q = new ArrayDeque <> ();
q . offer ( 0 );
vis [ 0 ] = true ;
for ( int ans = 0 ;; ++ ans ) {
for ( int k = q . size (); k > 0 ; -- k ) {
int i = q . poll ();
if ( i == n - 1 ) {
return ans ;
}
for ( int j : g . get ( arr [ i ] )) {
if ( ! vis [ j ] ) {
vis [ j ] = true ;
q . offer ( j );
}
}
g . get ( arr [ i ] ). clear ();
for ( int j : new int [] { i - 1 , i + 1 }) {
if ( 0 <= j && j < n && ! vis [ j ] ) {
vis [ j ] = true ;
q . offer ( j );
}
}
}
}
}
}
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 class Solution {
public :
int minJumps ( vector < int >& arr ) {
unordered_map < int , vector < int >> g ;
int n = arr . size ();
for ( int i = 0 ; i < n ; ++ i ) {
g [ arr [ i ]]. push_back ( i );
}
vector < bool > vis ( n );
queue < int > q {{ 0 }};
vis [ 0 ] = true ;
for ( int ans = 0 ;; ++ ans ) {
for ( int k = q . size (); k ; -- k ) {
int i = q . front ();
q . pop ();
if ( i == n - 1 ) {
return ans ;
}
for ( int j : g [ arr [ i ]]) {
if ( ! vis [ j ]) {
vis [ j ] = true ;
q . push ( j );
}
}
g [ arr [ i ]]. clear ();
for ( int j : { i - 1 , i + 1 }) {
if ( 0 <= j && j < n && ! vis [ j ]) {
vis [ j ] = true ;
q . push ( j );
}
}
}
}
}
};
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 func minJumps ( arr [] int ) int {
g := map [ int ][] int {}
for i , x := range arr {
g [ x ] = append ( g [ x ], i )
}
n := len ( arr )
q := [] int { 0 }
vis := make ([] bool , n )
vis [ 0 ] = true
for ans := 0 ; ; ans ++ {
for k := len ( q ); k > 0 ; k -- {
i := q [ 0 ]
q = q [ 1 :]
if i == n - 1 {
return ans
}
for _ , j := range g [ arr [ i ]] {
if ! vis [ j ] {
vis [ j ] = true
q = append ( q , j )
}
}
g [ arr [ i ]] = nil
for _ , j := range [] int { i - 1 , i + 1 } {
if 0 <= j && j < n && ! vis [ j ] {
vis [ j ] = true
q = append ( q , j )
}
}
}
}
}
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 function minJumps ( arr : number []) : number {
const g : Map < number , number [] > = new Map ();
const n = arr . length ;
for ( let i = 0 ; i < n ; ++ i ) {
if ( ! g . has ( arr [ i ])) {
g . set ( arr [ i ], []);
}
g . get ( arr [ i ]) ! . push ( i );
}
let q : number [] = [ 0 ];
const vis : boolean [] = Array ( n ). fill ( false );
vis [ 0 ] = true ;
for ( let ans = 0 ; ; ++ ans ) {
const nq : number [] = [];
for ( const i of q ) {
if ( i === n - 1 ) {
return ans ;
}
for ( const j of g . get ( arr [ i ]) ! ) {
if ( ! vis [ j ]) {
vis [ j ] = true ;
nq . push ( j );
}
}
g . get ( arr [ i ]) ! . length = 0 ;
for ( const j of [ i - 1 , i + 1 ]) {
if ( j >= 0 && j < n && ! vis [ j ]) {
vis [ j ] = true ;
nq . push ( j );
}
}
}
q = nq ;
}
}
GitHub