Find Latest Group of Size M
MedPrompt
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
arrare distinct.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. At each step, we update the binary string by setting a bit to '1' and then scan the entire string to find if any group of '1's has a length of exactly m.
Algorithm
-
- Initialize a boolean array
bitsof sizen+2(with padding for easier boundary checks) to allfalse.
- Initialize a boolean array
-
- Initialize a variable
latestStepto-1to store the result.
- Initialize a variable
-
- Iterate through the input array
arrfromstep = 0ton-1.
- Iterate through the input array
-
- In each iteration, get the position
pos = arr[step]and setbits[pos] = true.
- In each iteration, get the position
-
- After updating the
bitsarray, perform a full scan to check for the existence of any group of sizem.
- After updating the
-
- To do this, iterate from
i = 1ton, maintaining acountof consecutivetruebits. When afalsebit is encountered (or the end of the array is reached), it signifies the end of a group. Check if thecountof this group is exactlym.
- To do this, iterate from
-
- Keep a flag,
hasGroupOfM, which is set totrueif any group of sizemis found in the current step's configuration.
- Keep a flag,
-
- If
hasGroupOfMistrueafter the scan, updatelatestStepto the current step number (step + 1).
- If
-
- After the main loop finishes, return
latestStep.
- After the main loop finishes, return
Walkthrough
We use a boolean array, bits, to represent the binary string, initially all set to false (representing '0's). We loop from step 1 to n. In each step i, we find the position pos from arr[i-1] and set the corresponding bit bits[pos] to true. After each bit flip, we perform a complete scan of the bits array. During the scan, we count consecutive true values. A sequence of k ones is considered a 'group' if it's surrounded by false values or the array boundaries. If we find any group whose length is exactly m, we update our answer, latestStep, with the current step number. Since we want the latest such step, we continue this process until all bits are set, and the final value of latestStep will be our answer.
class Solution { public int findLatestStep(int[] arr, int m) { int n = arr.length; if (m > n) return -1; boolean[] bits = new boolean[n + 2]; // Use padding for easier boundary checks int latestStep = -1; for (int step = 0; step < n; step++) { int pos = arr[step]; bits[pos] = true; // Check if any group of size m exists at this step boolean hasGroupOfM = false; int count = 0; // Iterate up to n+1 to handle a group ending at position n for (int i = 1; i <= n + 1; i++) { if (bits[i]) { count++; } else { if (count == m) { hasGroupOfM = true; break; // Found a group, no need to check further for this step } count = 0; } } if (hasGroupOfM) { latestStep = step + 1; } } return latestStep; }}Complexity
Time
O(n^2), where `n` is the length of `arr`. The main loop runs `n` times, and inside it, we scan the `bits` array, which takes O(n) time. This results in a total time complexity of O(n*n).
Space
O(n) to store the `bits` array representing the binary string.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the logic from the problem description.
Cons
Highly inefficient due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints.
Solutions
Solution
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]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.