Find Latest Group of Size M - Practice Coding Problems

Find Latest Group of Size M - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: arr = [3,5,1,2,4], m = 3

› Output: 4

💡 Note: Step 1: 001000 (no groups of size 3), Step 2: 001010 (no groups of size 3), Step 3: 101010 (no groups of size 3), Step 4: 111010 (group of size 3 at positions 1-3), Step 5: 111110 (group of size 4, no size 3). Latest step with size 3 is step 4.

Example 2 — No Valid Group

$ Input: arr = [3,1,5,4,2], m = 3

› Output: -1

💡 Note: At no point during the process do we get exactly 3 consecutive 1's that cannot be extended further.

Example 3 — Early Formation

$ Input: arr = [1], m = 1

› Output: 1

💡 Note: After step 1: binary string becomes '1', which is a group of size 1.

Constraints

n == arr.length
1 ≤ n ≤ 10⁵
1 ≤ arr[i] ≤ n
All integers in arr are distinct
1 ≤ m ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input

Array [3,5,1,2,4] and target size m=3

Process

Set bits step by step, track group sizes

Output

Latest step (4) where group of size 3 exists

Key Takeaway

🎯 Key Insight: Track group sizes efficiently as bits are set, watching for the target size m

Asked in

F Facebook 15 G Google 12 a Amazon 8

The key insight is to efficiently track group sizes as bits are set, watching for exactly size m. The optimal approach uses a hash map to count groups of each size and updates them in O(1) time when merging adjacent groups. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation with String Reconstruction	O(n²)	O(n)	Simulate each step and rebuild binary string to find groups
Track Groups with HashMap	O(n)	O(n)	Efficiently track group sizes using hash map to count groups

Simulation with String Reconstruction — Algorithm Steps

Step 1: Initialize binary string with all zeros
Step 2: For each position in arr, set corresponding bit to '1'
Step 3: Scan string to find all consecutive groups of 1's
Step 4: Check if any group has exactly size m, update latest step

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with all zeros: 00000

Set Bits

Set arr[i] position to '1' at each step

Scan Groups

Find consecutive 1's and check sizes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr, int arrSize, int m) {
    char* binary = (char*)malloc((arrSize + 1) * sizeof(char));
    memset(binary, '0', arrSize);
    binary[arrSize] = '\0';
    int latest = -1;
    
    for (int step = 0; step < arrSize; step++) {
        int pos = arr[step] - 1; // Convert to 0-indexed
        binary[pos] = '1';
        
        // Find all groups of consecutive 1's
        int groups[1000];
        int groupCount = 0;
        int i = 0;
        while (i < arrSize) {
            if (binary[i] == '1') {
                int count = 0;
                while (i < arrSize && binary[i] == '1') {
                    count++;
                    i++;
                }
                groups[groupCount++] = count;
            } else {
                i++;
            }
        }
        
        // Check if any group has exactly size m
        for (int j = 0; j < groupCount; j++) {
            if (groups[j] == m) {
                latest = step + 1; // Convert back to 1-indexed
                break;
            }
        }
    }
    
    free(binary);
    return latest;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int arr[1000];
    int arrSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            arr[arrSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int m;
    scanf("%d", &m);
    
    int result = solution(arr, arrSize, m);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n steps, we scan the entire string of length n

⚠ Quadratic Growth

Space Complexity

O(n)

Binary string storage of size n

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation with String Reconstruction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler