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 given an integer m and you need to find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1s 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.
Example 3:
Input: arr = [1], m = 1
Output: 1
Example 4:
Input: arr = [2,1], m = 2
Output: 2
Constraints:
n == arr.length
1 <= n <= 10^5
1 <= arr[i] <= n
All integers in arr are distinct.
1 <= m <= arr.length
Solution:
UF
class Solution {
static class UF {
int[] sizes;
int[] parents;
Map<Integer, Integer> map;
public UF(int n) {
sizes = new int[n + 1];
parents = new int[n + 1];
map = new HashMap();
for (int i = 1; i <= n; i ++) {
parents[i] = i;
}
}
public int find(int x) {
while (x != parents[x]) {
parents[x] = parents[parents[x]];
x = parents[x];
}
return x;
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (sizes[rootX] > sizes[rootY]) {
map.put(sizes[rootX], map.get(sizes[rootX]) - 1);
map.put(sizes[rootY], map.get(sizes[rootY]) - 1);
sizes[rootX] += sizes[rootY];
map.put(sizes[rootX], map.getOrDefault(sizes[rootX], 0) + 1);
parents[rootY] = rootX;
} else {
map.put(sizes[rootX], map.get(sizes[rootX]) - 1);
map.put(sizes[rootY], map.get(sizes[rootY]) - 1);
sizes[rootY] += sizes[rootX];
map.put(sizes[rootY], map.getOrDefault(sizes[rootY], 0) + 1);
parents[rootX] = rootY;
}
}
}
public int findLatestStep(int[] arr, int m) {
int last = -1;
int n = arr.length;
Set<Integer> set = new HashSet();
UF uf = new UF(n);
for (int i = 0; i < n; i ++) {
int val = arr[i];
set.add(val);
uf.sizes[val] = 1;
uf.map.put(1, uf.map.getOrDefault(1, 0) + 1);
if (set.contains(val - 1)) {
uf.union(val, val - 1);
}
if (set.contains(val + 1)) {
uf.union(val, val + 1);
}
// System.out.println(uf.map);
if (uf.map.containsKey(m) && uf.map.get(m) > 0) {
last = i + 1;
}
}
return last;
}
}
class Solution {
public int findLatestStep(int[] arr, int m) {
int res = -1;
Map<Integer, Integer> left = new HashMap(), right = new HashMap();
int[] len = new int[arr.length + 1];
for (int i = 0; i < arr.length; i ++) {
int val = arr[i];
int l = left.getOrDefault(val - 1, 0), r = right.getOrDefault(val + 1, 0);
int newLen = l + r + 1;
if (l > 0) {
len[l] --;
left.remove(val - 1);
}
if (r > 0) {
len[r] --;
right.remove(val + 1);
}
left.put(val + r, newLen);
right.put(val - l, newLen);
len[newLen] ++;
if (len[m] > 0) {
res = i + 1;
}
}
return res;
}
}