Array
Hash Table
Binary Search
Simulation
Description
Given an array arr
that represents a permutation of numbers from 1
to n
.
You have a binary string of size n
that initially has all its bits set to zero. At each step i
(assuming both the binary string and arr
are 1-indexed) from 1
to n
, the bit at position arr[i]
is set to 1
.
You are also given an integer m
. Find the latest step at which there exists a group of ones of length m
. A group of ones is a contiguous substring of 1
's such that it cannot be extended in either direction.
Return the latest step at which there exists a group of ones of length exactly m
. If no such group exists, return -1
.
Example 1:
Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "001 00", groups: ["1"]
Step 2: "00101 ", groups: ["1", "1"]
Step 3: "1 0101", groups: ["1", "1", "1"]
Step 4: "11 101", groups: ["111", "1"]
Step 5: "1111 1", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.
Example 2:
Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation:
Step 1: "001 00", groups: ["1"]
Step 2: "1 0100", groups: ["1", "1"]
Step 3: "10101 ", groups: ["1", "1", "1"]
Step 4: "1011 1", groups: ["1", "111"]
Step 5: "11 111", groups: ["11111"]
No group of size 2 exists during any step.
Constraints:
n == arr.length
1 <= m <= n <= 105
1 <= arr[i] <= n
All integers in arr
are distinct .
Solutions
Solution 1
Python3 Java C++ Go JavaScript
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 class Solution :
def findLatestStep ( self , arr : List [ int ], m : int ) -> int :
def find ( x ):
if p [ x ] != x :
p [ x ] = find ( p [ x ])
return p [ x ]
def union ( a , b ):
pa , pb = find ( a ), find ( b )
if pa == pb :
return
p [ pa ] = pb
size [ pb ] += size [ pa ]
n = len ( arr )
if m == n :
return n
vis = [ False ] * n
p = list ( range ( n ))
size = [ 1 ] * n
ans = - 1
for i , v in enumerate ( arr ):
v -= 1
if v and vis [ v - 1 ]:
if size [ find ( v - 1 )] == m :
ans = i
union ( v , v - 1 )
if v < n - 1 and vis [ v + 1 ]:
if size [ find ( v + 1 )] == m :
ans = i
union ( v , v + 1 )
vis [ v ] = True
return ans
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 class Solution {
private int [] p ;
private int [] size ;
public int findLatestStep ( int [] arr , int m ) {
int n = arr . length ;
if ( m == n ) {
return n ;
}
boolean [] vis = new boolean [ n ] ;
p = new int [ n ] ;
size = new int [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
p [ i ] = i ;
size [ i ] = 1 ;
}
int ans = - 1 ;
for ( int i = 0 ; i < n ; ++ i ) {
int v = arr [ i ] - 1 ;
if ( v > 0 && vis [ v - 1 ] ) {
if ( size [ find ( v - 1 ) ] == m ) {
ans = i ;
}
union ( v , v - 1 );
}
if ( v < n - 1 && vis [ v + 1 ] ) {
if ( size [ find ( v + 1 ) ] == m ) {
ans = i ;
}
union ( v , v + 1 );
}
vis [ v ] = true ;
}
return ans ;
}
private int find ( int x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ] );
}
return p [ x ] ;
}
private void union ( int a , int b ) {
int pa = find ( a ), pb = find ( b );
if ( pa == pb ) {
return ;
}
p [ pa ] = pb ;
size [ pb ] += size [ pa ] ;
}
}
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 class Solution {
public :
vector < int > p ;
vector < int > size ;
int findLatestStep ( vector < int >& arr , int m ) {
int n = arr . size ();
if ( m == n ) return n ;
p . resize ( n );
size . assign ( n , 1 );
for ( int i = 0 ; i < n ; ++ i ) p [ i ] = i ;
int ans = -1 ;
vector < int > vis ( n );
for ( int i = 0 ; i < n ; ++ i ) {
int v = arr [ i ] - 1 ;
if ( v && vis [ v - 1 ]) {
if ( size [ find ( v - 1 )] == m ) ans = i ;
unite ( v , v - 1 );
}
if ( v < n - 1 && vis [ v + 1 ]) {
if ( size [ find ( v + 1 )] == m ) ans = i ;
unite ( v , v + 1 );
}
vis [ v ] = true ;
}
return ans ;
}
int find ( int x ) {
if ( p [ x ] != x ) p [ x ] = find ( p [ x ]);
return p [ x ];
}
void unite ( int a , int b ) {
int pa = find ( a ), pb = find ( b );
if ( pa == pb ) return ;
p [ pa ] = pb ;
size [ pb ] += size [ pa ];
}
};
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 func findLatestStep ( arr [] int , m int ) int {
n := len ( arr )
if m == n {
return n
}
p := make ([] int , n )
size := make ([] int , n )
vis := make ([] bool , n )
for i := range p {
p [ i ] = i
size [ i ] = 1
}
var find func ( int ) int
find = func ( x int ) int {
if p [ x ] != x {
p [ x ] = find ( p [ x ])
}
return p [ x ]
}
union := func ( a , b int ) {
pa , pb := find ( a ), find ( b )
if pa == pb {
return
}
p [ pa ] = pb
size [ pb ] += size [ pa ]
}
ans := - 1
for i , v := range arr {
v --
if v > 0 && vis [ v - 1 ] {
if size [ find ( v - 1 )] == m {
ans = i
}
union ( v , v - 1 )
}
if v < n - 1 && vis [ v + 1 ] {
if size [ find ( v + 1 )] == m {
ans = i
}
union ( v , v + 1 )
}
vis [ v ] = true
}
return ans
}
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 const findLatestStep = function ( arr , m ) {
function find ( x ) {
if ( p [ x ] !== x ) {
p [ x ] = find ( p [ x ]);
}
return p [ x ];
}
function union ( a , b ) {
const pa = find ( a );
const pb = find ( b );
if ( pa === pb ) {
return ;
}
p [ pa ] = pb ;
size [ pb ] += size [ pa ];
}
const n = arr . length ;
if ( m === n ) {
return n ;
}
const vis = Array ( n ). fill ( false );
const p = Array . from ({ length : n }, ( _ , i ) => i );
const size = Array ( n ). fill ( 1 );
let ans = - 1 ;
for ( let i = 0 ; i < n ; ++ i ) {
const v = arr [ i ] - 1 ;
if ( v > 0 && vis [ v - 1 ]) {
if ( size [ find ( v - 1 )] === m ) {
ans = i ;
}
union ( v , v - 1 );
}
if ( v < n - 1 && vis [ v + 1 ]) {
if ( size [ find ( v + 1 )] === m ) {
ans = i ;
}
union ( v , v + 1 );
}
vis [ v ] = true ;
}
return ans ;
};
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution :
def findLatestStep ( self , arr : List [ int ], m : int ) -> int :
n = len ( arr )
if m == n :
return n
cnt = [ 0 ] * ( n + 2 )
ans = - 1
for i , v in enumerate ( arr ):
v -= 1
l , r = cnt [ v - 1 ], cnt [ v + 1 ]
if l == m or r == m :
ans = i
cnt [ v - l ] = cnt [ v + r ] = l + r + 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public int findLatestStep ( int [] arr , int m ) {
int n = arr . length ;
if ( m == n ) {
return n ;
}
int [] cnt = new int [ n + 2 ] ;
int ans = - 1 ;
for ( int i = 0 ; i < n ; ++ i ) {
int v = arr [ i ] ;
int l = cnt [ v - 1 ] , r = cnt [ v + 1 ] ;
if ( l == m || r == m ) {
ans = i ;
}
cnt [ v - l ] = l + r + 1 ;
cnt [ v + r ] = l + r + 1 ;
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution {
public :
int findLatestStep ( vector < int >& arr , int m ) {
int n = arr . size ();
if ( m == n ) return n ;
vector < int > cnt ( n + 2 );
int ans = -1 ;
for ( int i = 0 ; i < n ; ++ i ) {
int v = arr [ i ];
int l = cnt [ v - 1 ], r = cnt [ v + 1 ];
if ( l == m || r == m ) ans = i ;
cnt [ v - l ] = cnt [ v + r ] = l + r + 1 ;
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 func findLatestStep ( arr [] int , m int ) int {
n := len ( arr )
if m == n {
return n
}
cnt := make ([] int , n + 2 )
ans := - 1
for i , v := range arr {
l , r := cnt [ v - 1 ], cnt [ v + 1 ]
if l == m || r == m {
ans = i
}
cnt [ v - l ], cnt [ v + r ] = l + r + 1 , l + r + 1
}
return ans
}