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
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
}
GitHub