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] <= narr are distinct.Problem Overview: You receive an array arr where arr[i] marks the position flipped from 0 to 1 at step i. After each step, groups of consecutive 1s form. The task is to return the latest step where at least one group has length exactly m.
Approach 1: Array Simulation for Borders (O(n) time, O(n) space)
This approach simulates group formation using a length array that stores the size of a contiguous group only at its boundaries. When position pos flips to 1, check the group size to the left and right using the boundary array. The new merged group length becomes left + right + 1. Update the boundaries at pos - left and pos + right with the new size. Track how many groups currently have size m and update the latest step whenever the count is positive. Each index is processed once, and group lengths are updated in constant time, giving O(n) time and O(n) space. This technique relies on efficient boundary updates in an array while simulating the process step by step, similar to problems in simulation.
Approach 2: Union-Find (O(n α(n)) time, O(n) space)
Another way to track connected components of 1s is using a disjoint-set (Union-Find) structure. Each time a position flips to 1, mark it active and union it with its active neighbors (left and right). The union operation merges components and updates their sizes. Maintain a counter for components whose size equals m. When two components merge, decrement counts for old sizes and increment for the new size if needed. Union-Find operations run in nearly constant time with path compression and union by rank, giving O(n α(n)) time and O(n) space. This approach models the problem as dynamic connectivity and works well when you think in terms of merging segments rather than updating boundaries directly. The structure behaves similarly to techniques used in hash table or connectivity problems.
Recommended for interviews: The boundary array simulation is the expected solution. It achieves strict O(n) time and avoids the overhead of Union-Find. Interviewers usually look for the key insight: store group lengths only at the boundaries so you can merge segments in constant time. Mentioning the Union-Find alternative shows you understand dynamic connectivity problems, but implementing the boundary technique demonstrates stronger problem-solving insight.
This approach uses an array to simulate the process and keep track of the consecutive ones. It maintains two main arrays: length and count. The length array records the number of consecutive ones at the start and end of each group, while the count array keeps track of how many groups of each length exist during the process.
When setting a bit from 0 to 1, we check its neighbors to see if we can merge segments or create a new group. We update the length and count arrays accordingly, and check if there exists any group of size m.
This Python solution uses an array named length to track the sizes of groups of ones at their boundaries. Each time we set a bit at pos, we determine if it should merge with any adjacent groups of ones or create a new group. We maintain a count array to track how many groups of each length exist. If at any point, the count of groups of length m is greater than 0, we update the result to be the current step index i + 1.
Time Complexity: O(n), where n is the number of elements in arr, due to the constant time operations for each step.
Space Complexity: O(n), for storing the length and count arrays.
The union-find data structure is useful for handling the merging process of groups efficiently. In this approach, we use an array to represent the parent of each node and another array to store the size of each group. As we iterate through the array and set a bit to 1, we connect the new bit to its neighboring ones using union operations. We track the sizes of the groups and update accordingly. The largest step index where a group of size m is found is returned.
This Java solution employs the union-find data structure to efficiently merge adjacent groups when a new bit is set to 1. The parent array helps identify the root of each group, and the size array tracks the size of the groups.
Java
JavaScript
Time Complexity: O(n log n), because union-find operations are nearly constant time when using path compression and union by size.
Space Complexity: O(n), for the union-find data structures.
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Array Simulation for Borders | Time Complexity: O(n), where n is the number of elements in |
| Approach 2: Union-Find | Time Complexity: O(n log n), because union-find operations are nearly constant time when using path compression and union by size. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array Boundary Simulation | O(n) | O(n) | Best general solution. Efficient when simulating dynamic group formation step by step. |
| Union-Find (Disjoint Set) | O(n α(n)) | O(n) | Useful when thinking in terms of merging connected components or solving dynamic connectivity problems. |
LeetCode 1562. Find Latest Group of Size M (Python) • AH Tech • 1,317 views views
Watch 7 more video solutions →Practice Find Latest Group of Size M with our built-in code editor and test cases.
Practice on FleetCode