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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Latest Group of Size M

Difficulty: Medium

Problem Description

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 exactly m. If no such group exists, return -1.

Key Insights

  • A group of ones is defined as a contiguous substring of 1's that cannot be extended in either direction.
  • The goal is to track the formation of groups of ones as we process each element in arr.
  • We need to efficiently determine when a group of exactly m ones exists after each step.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use an array to represent the binary string, initializing it with zeros. As we process each element in the arr, we set the corresponding position in the binary string to 1. We will also need to maintain a count of the size of contiguous groups of 1's as we update the binary string. We can do this by checking the left and right neighbors of the newly set bit to determine if it forms or extends a group of 1's.

  1. Initialize a binary array of size n with all elements set to 0.
  2. Iterate over each element in arr and update the binary array.
  3. After each update, check for groups of 1's:
    • If the current bit is set to 1, check the lengths of contiguous 1's that it connects.
    • Keep track of the latest step where a group of exactly m 1's exists.
  4. Return the latest step or -1 if no such group exists.

Code Solutions

def findLatestStep(arr, m):
    n = len(arr)
    binary = [0] * n
    latest_step = -1
    count = [0] * (n + 2)  # Use count array to track the size of groups
    
    for step in range(n):
        pos = arr[step] - 1
        binary[pos] = 1
        
        left = pos + 1
        right = pos + 1
        
        # Count the length of the group to the left
        while left > 0 and binary[left - 1] == 1:
            left -= 1
        # Count the length of the group to the right
        while right < n and binary[right] == 1:
            right += 1
        
        # The length of the current group
        current_length = right - left
        
        # Update the count of group sizes
        count[current_length] += 1
        
        # Check if we have a group of size m
        if count[m] > 0:
            latest_step = step + 1  # Store the latest step (1-indexed)
        
        # Reset the count for the current length
        count[current_length] = 0
    
    return latest_step
← Back to All Questions