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: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", 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: "00100", groups: ["1"]
Step 2: "10100", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "10111", groups: ["1", "111"]
Step 5: "11111", groups: ["11111"]
No group of size 2 exists during any step.
Constraints:
n == arr.length1 <= m <= n <= 1051 <= arr[i] <= n- All integers in
arr are distinct.
Solutions#
Solution 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
| 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
}
|
Solution 2#
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
}
|
