Problem Description

You are given two integers, n and m, and an array arr of length n where arr[i] represents the position (1-indexed) that is set to 1 at step i+1. Initially, all positions from 1 to n are set to 0. At each step, you set arr[i] to 1. After each step, the array is split into groups of consecutive 1's. Your task is to find the latest step (1-indexed) at which there exists a group of consecutive 1's of length exactly m. If no such group exists at any step, return -1.

• Each position is set to 1 exactly once.
• Do not reuse positions or steps.
• Return the latest step (not the first) where a group of length m exists.

Thought Process

At first glance, it seems we could simulate the process step by step, updating the array and checking for groups of 1's of length m after each update. However, this brute-force approach would be inefficient, especially for large n, as it would require scanning the entire array after each step.

To optimize, we need a way to efficiently track the lengths of groups of 1's as we set positions to 1. Noticing that only the groups adjacent to the newly set position are affected, we can focus our updates and checks only on those areas.

This leads us to use a data structure (like a hash map or array) to record the length of groups at their boundaries. By updating only the affected boundaries, we can keep track of group sizes and efficiently determine if a group of length m exists after each step.

Solution Approach

• Step 1: Initialize Structures
  • We use an array lengths of size n+2 to store the length of the group at each boundary (leftmost and rightmost points).
  • We also use a counter (e.g., a hash map or array) to track how many groups of size m currently exist.
• Step 2: Simulate the Steps
  • For each step, when setting arr[i] to 1, check the length of the group to the left and right (using lengths at pos-1 and pos+1).
  • The new group size is the sum of left and right group sizes plus one (for the current position).
  • Update the leftmost and rightmost boundaries of the new group in lengths to reflect the new group size.
  • If any groups of size m are merged or split, update the counter accordingly.
• Step 3: Track the Latest Step
  • After each step, if there is at least one group of size m, record the current step as a candidate for the answer.
  • Continue this process for all steps, and return the last step where such a group exists.
• Why This Works:
  • We only update at the group boundaries, making each step O(1) time.
  • By tracking group sizes at boundaries, we avoid re-scanning the entire array.

Example Walkthrough

Example:
arr = [3,5,1,2,4], n = 5, m = 1

1. Step 1: Set position 3 to 1. Groups: [0,0,1,0,0]. Groups of size 1: {3}. Latest step = 1.
2. Step 2: Set position 5 to 1. Groups: [0,0,1,0,1]. Groups of size 1: {3,5}. Latest step = 2.
3. Step 3: Set position 1 to 1. Groups: [1,0,1,0,1]. Groups of size 1: {1,3,5}. Latest step = 3.
4. Step 4: Set position 2 to 1. Groups: [1,1,1,0,1]. Now, positions 1 and 2 form a group of size 2; position 3 is part of the group. So group: [1,1,1]. No group of size 1. Latest step remains 3.
5. Step 5: Set position 4 to 1. All positions are now 1. Single group of size 5. No group of size 1. Latest step remains 3.

Output: 3

At step 3, there was at least one group of size 1. After that, no such group exists.

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(n²) — for each of n steps, scan the array to find all groups.
  • Space Complexity: O(n) — to store the array.
• Optimized Approach (Boundary Tracking):
  • Time Complexity: O(n) — each step only updates group boundaries and counters in constant time.
  • Space Complexity: O(n) — to store group lengths and counters.

The optimized approach is efficient and suitable for large inputs.

Code Implementation

class Solution:
    def findLatestStep(self, arr, m):
        n = len(arr)
        if m == n:
            return n
        lengths = [0] * (n + 2)
        count = [0] * (n + 2)
        res = -1
        for step, pos in enumerate(arr):
            left = lengths[pos - 1]
            right = lengths[pos + 1]
            group_len = left + right + 1
            lengths[pos - left] = lengths[pos + right] = group_len
            count[left] -= 1
            count[right] -= 1
            count[group_len] += 1
            if count[m] > 0:
                res = step + 1
        return res
      

class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size();
        if (m == n) return n;
        vector<int> lengths(n + 2, 0);
        vector<int> count(n + 2, 0);
        int res = -1;
        for (int step = 0; step < n; ++step) {
            int pos = arr[step];
            int left = lengths[pos - 1];
            int right = lengths[pos + 1];
            int group_len = left + right + 1;
            lengths[pos - left] = lengths[pos + right] = group_len;
            count[left]--;
            count[right]--;
            count[group_len]++;
            if (count[m] > 0) res = step + 1;
        }
        return res;
    }
};
      

class Solution {
    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        if (m == n) return n;
        int[] lengths = new int[n + 2];
        int[] count = new int[n + 2];
        int res = -1;
        for (int step = 0; step < n; step++) {
            int pos = arr[step];
            int left = lengths[pos - 1];
            int right = lengths[pos + 1];
            int groupLen = left + right + 1;
            lengths[pos - left] = lengths[pos + right] = groupLen;
            count[left]--;
            count[right]--;
            count[groupLen]++;
            if (count[m] > 0) res = step + 1;
        }
        return res;
    }
}
      

var findLatestStep = function(arr, m) {
    const n = arr.length;
    if (m === n) return n;
    const lengths = new Array(n + 2).fill(0);
    const count = new Array(n + 2).fill(0);
    let res = -1;
    for (let step = 0; step < n; step++) {
        const pos = arr[step];
        const left = lengths[pos - 1];
        const right = lengths[pos + 1];
        const groupLen = left + right + 1;
        lengths[pos - left] = lengths[pos + right] = groupLen;
        count[left]--;
        count[right]--;
        count[groupLen]++;
        if (count[m] > 0) res = step + 1;
    }
    return res;
};
      

Summary

The key insight for solving the "Find Latest Group of Size M" problem is to efficiently track group sizes at their boundaries using an auxiliary array. By updating only the affected group boundaries and maintaining a count of groups of size m, we avoid unnecessary rescanning and achieve an optimal O(n) solution. This approach elegantly balances correctness and efficiency, making it suitable for large input sizes and demonstrating the power of boundary-based group tracking in array problems.