We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Latest Group of Size M

Number: 1684

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array arr representing a permutation of numbers from 1 to n, we simulate a binary string of length n that starts with all zeros. At each step i (using 1-indexing for both arr and the binary string), the bit at position arr[i] is set to 1. We must determine the latest step (i.e., the maximum step index) at which there exists a contiguous group of 1s of exactly length m. If such a group never exists, return -1.

Key Insights

  • Instead of simulating the entire string at every step, we maintain information about contiguous segments (groups) of 1s.
  • Use an auxiliary array (or similar data structure) to store the length of the segment at the boundaries.
  • When a bit changes to 1, check its left and right neighbors to merge segments if they exist.
  • Maintain a count of segments that are exactly of length m. When merging segments, update the counts accordingly.
  • This efficient approach ensures that each insertion only requires constant time checks and updates.

Space and Time Complexity

Time Complexity: O(n), as each insertion and merge operation is performed in constant time. Space Complexity: O(n), due to the auxiliary arrays used to track segment boundaries and counts.

Solution

We simulate the process by keeping track of contiguous segments using an extra array that marks the length of each segment at its boundaries. For each step:

  1. Retrieve the segment lengths immediately to the left and right of the bit that is being flipped.
  2. Combine these lengths with the current bit to form a new segment.
  3. Update the boundaries of the new segment.
  4. Adjust the count for segments of exactly length m by decrementing counts for segments that are merged and increasing if the new segment is of size m.
  5. Record the step if any segment of size m exists. The final answer is the last step (1-indexed) when such a segment exists.

Code Solutions

# Python solution with detailed comments
class Solution:
    def findLatestStep(self, arr: list[int], m: int) -> int:
        n = len(arr)
        # Special case: if m equals n, the only valid step is when the entire array is filled
        if m == n: 
            return n
        
        # Initialize an auxiliary array to keep track of group lengths at boundaries.
        # We use n + 2 to simplify boundary handling.
        length = [0] * (n + 2)
        # Array to count how many groups exist for a given length
        count = [0] * (n + 1)
        result = -1
        
        # Process each step where we set bit at position pos to 1
        for step, pos in enumerate(arr):
            # Get lengths of contiguous groups adjacent to the current pos
            left_length = length[pos - 1]
            right_length = length[pos + 1]
            # Calculate new group length formed by merging left, current bit, and right group
            new_length = left_length + right_length + 1
            
            # Update boundaries for the new group
            length[pos - left_length] = new_length
            length[pos + right_length] = new_length
            
            # If the left or right groups were exactly length m, decrement the count,
            # because they are merged into a larger group.
            if left_length == m:
                count[m] -= 1
            if right_length == m:
                count[m] -= 1
            
            # If the new group length is exactly m, increase the count
            if new_length == m:
                count[m] += 1
            
            # If any group of size m exists after this step, record the step (1-indexed)
            if count[m] > 0:
                result = step + 1
        
        return result

# Example usage:
# sol = Solution()
# print(sol.findLatestStep([3,5,1,2,4], 1))  # Expected Output: 4
← Back to All Questions