Find Latest Group of Size M

Med

#1438Time: O(n^2), where `n` is the length of `arr`. The main loop runs `n` times, and inside it, we scan the `bits` array, which takes O(n) time. This results in a total time complexity of O(n*n).Space: O(n) to store the `bits` array representing the binary string.

Algorithms

Binary Search

Data structures

Array Hash Table

Prompt

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 <= 10⁵
1 <= arr[i] <= n
All integers in arr are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. At each step, we update the binary string by setting a bit to '1' and then scan the entire string to find if any group of '1's has a length of exactly m.

Algorithm

1. Initialize a boolean array bits of size n+2 (with padding for easier boundary checks) to all false.
1. Initialize a variable latestStep to -1 to store the result.
1. Iterate through the input array arr from step = 0 to n-1.
1. In each iteration, get the position pos = arr[step] and set bits[pos] = true.
1. After updating the bits array, perform a full scan to check for the existence of any group of size m.
1. To do this, iterate from i = 1 to n, maintaining a count of consecutive true bits. When a false bit is encountered (or the end of the array is reached), it signifies the end of a group. Check if the count of this group is exactly m.
1. Keep a flag, hasGroupOfM, which is set to true if any group of size m is found in the current step's configuration.
1. If hasGroupOfM is true after the scan, update latestStep to the current step number (step + 1).
1. After the main loop finishes, return latestStep.

Walkthrough

We use a boolean array, bits, to represent the binary string, initially all set to false (representing '0's). We loop from step 1 to n. In each step i, we find the position pos from arr[i-1] and set the corresponding bit bits[pos] to true. After each bit flip, we perform a complete scan of the bits array. During the scan, we count consecutive true values. A sequence of k ones is considered a 'group' if it's surrounded by false values or the array boundaries. If we find any group whose length is exactly m, we update our answer, latestStep, with the current step number. Since we want the latest such step, we continue this process until all bits are set, and the final value of latestStep will be our answer.

1class Solution {2    public int findLatestStep(int[] arr, int m) {3        int n = arr.length;4        if (m > n) return -1;5        6        boolean[] bits = new boolean[n + 2]; // Use padding for easier boundary checks7        int latestStep = -1;8        9        for (int step = 0; step < n; step++) {10            int pos = arr[step];11            bits[pos] = true;12            13            // Check if any group of size m exists at this step14            boolean hasGroupOfM = false;15            int count = 0;16            // Iterate up to n+1 to handle a group ending at position n17            for (int i = 1; i <= n + 1; i++) { 18                if (bits[i]) {19                    count++;20                } else {21                    if (count == m) {22                        hasGroupOfM = true;23                        break; // Found a group, no need to check further for this step24                    }25                    count = 0;26                }27            }28            29            if (hasGroupOfM) {30                latestStep = step + 1;31            }32        }33        34        return latestStep;35    }36}

Complexity

Time

O(n^2), where `n` is the length of `arr`. The main loop runs `n` times, and inside it, we scan the `bits` array, which takes O(n) time. This results in a total time complexity of O(n*n).

Space

O(n) to store the `bits` array representing the binary string.

Trade-offs

Pros

Simple to understand and implement.
Directly follows the logic from the problem description.

Cons

Highly inefficient due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints.

Instead of re-scanning the entire array at each step, we can maintain the lengths of the groups of ones in a more efficient way. When a new '1' is placed, it can merge with adjacent groups. We only need to track the lengths of these groups and how many groups of length m exist at any time.

Algorithm

1. Initialize an array length of size n+2 with all zeros. length[i] will store the length of a group of ones if i is a boundary of that group.
1. Initialize an array count of size n+1 with all zeros. count[k] will store the number of groups of length k.
1. Initialize latestStep = -1.
1. Iterate from step = 1 to n:
- a. Get the current position pos = arr[step-1] where a '1' is being placed.
- b. Find the length of the group to the left, leftLen = length[pos-1], and to the right, rightLen = length[pos+1].
- c. These two groups (if they exist) will be merged with the new '1'. Decrement the counts for their lengths: count[leftLen]-- and count[rightLen]--.
- d. Calculate the length of the new merged group: newLen = leftLen + rightLen + 1.
- e. Increment the count for this new length: count[newLen]++.
- f. Update the length array at the boundaries of this new group: length[pos - leftLen] = newLen and length[pos + rightLen] = newLen.
- g. Check if count[m] is greater than 0. If it is, it means at least one group of length m exists at the current step, so update latestStep = step.
1. After the loop, return latestStep.

Walkthrough

This optimized approach avoids the expensive O(n) scan at each step. We use two auxiliary arrays: length and count. The length array stores the length of a group of ones at its boundaries. For example, if there is a group of ones from index i to j, we set length[i] = length[j] = (j - i + 1). The count array acts as a frequency map, where count[k] stores how many groups of length k currently exist.

As we iterate through the steps, placing a '1' at position pos, we look at its neighbors pos-1 and pos+1. The length values at these positions tell us the lengths of the adjacent groups. We use this information to calculate the length of the new, merged group. We then update the count array by decrementing the counts for the old groups that were just merged and incrementing the count for the new group. Finally, we update the length array at the new boundaries. By checking count[m] at each step, we can efficiently determine if a group of the target size exists and update our result accordingly.

1class Solution {2    public int findLatestStep(int[] arr, int m) {3        int n = arr.length;4        if (m > n) {5            return -1;6        }7        8        // length[i] stores the length of the group of 1s which has i as a boundary9        int[] length = new int[n + 2]; 10        // count[k] stores the number of groups of length k11        int[] count = new int[n + 1];12        13        int latestStep = -1;14        15        for (int step = 1; step <= n; step++) {16            int pos = arr[step - 1];17            18            int leftLen = length[pos - 1];19            int rightLen = length[pos + 1];20            21            int newLen = leftLen + rightLen + 1;22            23            // Update length at the boundaries of the new group24            length[pos - leftLen] = newLen;25            length[pos + rightLen] = newLen;26            27            // Update counts of groups28            if (leftLen > 0) {29                count[leftLen]--;30            }31            if (rightLen > 0) {32                count[rightLen]--;33            }34            count[newLen]++;35            36            // Check if there is any group of size m37            if (count[m] > 0) {38                latestStep = step;39            }40        }41        42        return latestStep;43    }44}

Complexity

Time

O(n), where `n` is the length of `arr`. We iterate through the input array once, and all operations inside the loop (array lookups and updates) are constant time.

Space

O(n) to store the `length` and `count` arrays, both of which are proportional to the input size `n`.

Trade-offs

Pros

Very efficient, with a linear time complexity.
Easily handles the largest possible inputs within the time limits.

Cons

More complex to reason about and implement compared to the brute-force approach.
Requires two extra arrays, increasing space usage, though still linear.

Solutions

Solution

1class Solution {2private3  int[] p;4private5  int[] size;6public7  int findLatestStep(int[] arr, int m) {8    int n = arr.length;9    if (m == n) {10      return n;11    }12    boolean[] vis = new boolean[n];13    p = new int[n];14    size = new int[n];15    for (int i = 0; i < n; ++i) {16      p[i] = i;17      size[i] = 1;18    }19    int ans = -1;20    for (int i = 0; i < n; ++i) {21      int v = arr[i] - 1;22      if (v > 0 && vis[v - 1]) {23        if (size[find(v - 1)] == m) {24          ans = i;25        }26        union(v, v - 1);27      }28      if (v < n - 1 && vis[v + 1]) {29        if (size[find(v + 1)] == m) {30          ans = i;31        }32        union(v, v + 1);33      }34      vis[v] = true;35    }36    return ans;37  }38private39  int find(int x) {40    if (p[x] != x) {41      p[x] = find(p[x]);42    }43    return p[x];44  }45private46  void union(int a, int b) {47    int pa = find(a), pb = find(b);48    if (pa == pb) {49      return;50    }51    p[pa] = pb;52    size[pb] += size[pa];53  }54}

1const findLatestStep = function ( arr , m ) { function find ( x ) { if ( p [ x ] !== x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } function union ( a , b ) { const pa = find ( a ); const pb = find ( b ); if ( pa === pb ) { return ; } p [ pa ] = pb ; size [ pb ] += size [ pa ]; } const n = arr . length ; if ( m === n ) { return n ; } const vis = Array ( n ). fill ( false ); const p = Array . from ({ length : n }, ( _ , i ) => i ); const size = Array ( n ). fill ( 1 ); let ans = - 1 ; for ( let i = 0 ; i < n ; ++ i ) { const v = arr [ i ] - 1 ; if ( v > 0 && vis [ v - 1 ]) { if ( size [ find ( v - 1 )] === m ) { ans = i ; } union ( v , v - 1 ); } if ( v < n - 1 && vis [ v + 1 ]) { if ( size [ find ( v + 1 )] === m ) { ans = i ; } union ( v , v + 1 ); } vis [ v ] = true ; } return ans ; };

1class Solution {2public:3  vector<int> p;4  vector<int> size;5  int findLatestStep(vector<int> &arr, int m) {6    int n = arr.size();7    if (m == n)8      return n;9    p.resize(n);10    size.assign(n, 1);11    for (int i = 0; i < n; ++i)12      p[i] = i;13    int ans = -1;14    vector<int> vis(n);15    for (int i = 0; i < n; ++i) {16      int v = arr[i] - 1;17      if (v && vis[v - 1]) {18        if (size[find(v - 1)] == m)19          ans = i;20        unite(v, v - 1);21      }22      if (v < n - 1 && vis[v + 1]) {23        if (size[find(v + 1)] == m)24          ans = i;25        unite(v, v + 1);26      }27      vis[v] = true;28    }29    return ans;30  }31  int find(int x) {32    if (p[x] != x)33      p[x] = find(p[x]);34    return p[x];35  }36  void unite(int a, int b) {37    int pa = find(a), pb = find(b);38    if (pa == pb)39      return;40    p[pa] = pb;41    size[pb] += size[pa];42  }43};

1class Solution:2    def findLatestStep(self, arr: List[int], m: int) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(a, b): pa, pb = find(a), find(b) if pa == pb: return p[pa] = pb size[pb] += size[pa] n = len(arr) if m == n: return n vis = [False] * n p = list(range(n)) size = [1] * n ans = - 1 for i, v in enumerate(arr): v -= 1 if v and vis[v - 1]: if size[find(v - 1)] == m: ans = i union(v, v - 1) if v < n - 1 and vis[v + 1]: if size[find(v + 1)] == m: ans = i union(v, v + 1) vis[v] = True return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem