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 exactlym. 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
class Solution {
public int find(int[] parent, int node) {
if (node != parent[node])
parent[node] = find(parent, parent[node]);
return parent[node];
}
public int findLatestStep(int[] arr, int m) {
int n = arr.length;
// Parent array for DSU
int[] parent = new int[n];
// Map of parent -> Size of group of that parent
Map<Integer, Integer> map = new HashMap<>();
char[] str = new char[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
str[i] = '0';
}
int ans = -1, countOfMGroups = 0;
for (int i = 0; i < n; i++) {
// Current parent
int p = arr[i] - 1;
// Initialising group size of this parent
map.put(p, 1);
str[p] = '1';
// Joining process
if (arr[i] - 2 >= 0 && str[arr[i] - 2] == '1') {
int p1 = find(parent, arr[i] - 2);
// This group size will be increased
if (map.get(p1) == m)
countOfMGroups--;
map.put(p1, map.get(p1) + 1);
map.remove(p);
parent[p] = p1;
p = p1;
}
if (arr[i] < n && str[arr[i]] == '1') {
int p2 = find(parent, arr[i]);
// This group will be merged with others to form a bigger group
if (map.get(p2) == m)
countOfMGroups--;
map.put(p, map.get(p) + map.get(p2));
map.remove(p2);
parent[p2] = p;
}
if (map.get(p) == m)
countOfMGroups++;
if (countOfMGroups > 0)
ans = i + 1;
}
return ans;
}
}