Skip to main content
Talentd

Find Latest Group of Size M - Solution & Explanation

MediumArrayHash TableBinary SearchSimulation12 min readAsked at: Google
Practice this problem

Problem Statement

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.length
  • 1 <= m <= n <= 105
  • 1 <= arr[i] <= n
  • All integers in arr are distinct.

Approach Overview

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.

Approach 1: Approach 1: Using Array Simulation for Borders

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Union-Find

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Array Simulation for Borders

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.

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.
Space Complexity: O(n), for the union-find data structures.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Array Boundary SimulationO(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.

Video Solution

Leetcode Weekly Contest 203 || PROBELM 1560 , 1561 , 1562 || LEETCODE • code Explainer • 2,474 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Find Latest Group of Size M easy or hard?
The problem is rated Medium because the main challenge is discovering the boundary-length trick. Once the insight is clear, the implementation becomes straightforward and runs in linear time.
Find Latest Group of Size M Python/Java solution
Python and C++ implementations commonly use the boundary array simulation technique for an O(n) solution. Java and JavaScript versions often demonstrate the union-find approach, which also runs close to linear time with path compression.
How to solve Find Latest Group of Size M in O(n)?
Maintain an array where only the boundaries of each group store the group's length. When a new position becomes 1, read the left and right group lengths, compute the merged size, and update the new boundaries. Track how many groups have size m and update the latest step whenever such a group exists.
What is the best approach for Find Latest Group of Size M?
The most efficient approach uses boundary length simulation with an array. Each time a position flips to 1, you check the lengths of adjacent groups and merge them in O(1). This produces an overall O(n) time and O(n) space solution while tracking how many groups of size m exist after each step.
Is Find Latest Group of Size M asked at Google/Amazon/Meta?
Problems involving dynamic segment merging and union-find structures appear frequently in interviews at companies like Amazon and Google. Variants of this question test understanding of union-find, interval merging, and efficient array simulation.
What data structure is used in Find Latest Group of Size M?
Common solutions use an array to store boundary lengths of groups or a Union-Find (disjoint set) structure to maintain connected components of 1s. Both approaches efficiently track group sizes as new positions are activated.
What is the time complexity of Find Latest Group of Size M?
The optimal solution runs in O(n) time because each element is processed once and group merges are constant-time operations. Space complexity is O(n) for storing the boundary lengths or union-find structures used to track group sizes.

Ready to solve this problem?

Practice Find Latest Group of Size M with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays