1562. Find Latest Group of Size M


Problem Description

In this problem, we are given an array arr that is a permutation of numbers from 1 to n, meaning it contains all integers in that range exactly once. We also have a binary string of size n starting with all zeroes. We follow steps from 1 to n, where at each step i, we set the bit at position arr[i] to 1.

We are tasked with finding the latest step at which there is a contiguous group of 1s in the binary string that is exactly of length m. A group of 1s can be considered a substring of the binary string that consists only of 1s and cannot be extended further on either side without encountering a 0. If we cannot find such a group at any step, the function should return -1.

Intuition

The intuition behind the solution lies in leveraging the properties of the contiguous groups of 1s and keeping track of their lengths as the binary array is updated. Here's how we approach the problem:

  1. Notice that if m equals n, the answer would be n because we can only form a contiguous group of 1s of length n at the last step.

  2. Initialize an array cnt to keep track of the lengths of contiguous groups of 1s. The size of this array is n + 2 to handle edge cases involving the first and last elements without going out of bounds.

  3. Iterate through the arr array, decrementing the value of each arr[i] by one to match the 0-based indexing of the cnt array.

  4. At each step, we detect the lengths of contiguous groups to the left and right of the current position. We do this by looking at the cnt array at the positions immediately before and after the current bit's position.

  5. If either the left or right contiguous group of 1s is of length m, we update the answer to the current step, as this step represents the latest occurrence of a group of length m.

  6. We update the cnt array to reflect the changes in the lengths of contiguous groups of 1s. The new length is the sum of the lengths of the contiguous groups to the left and right, plus one for the current bit being set to 1.

The algorithm efficiently keeps track of the sizes of contiguous groups of 1s at each turn and updates the answer when the group of size m is affected. This provides us the latest step when such a group exists.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What data structure does Breadth-first search typically uses to store intermediate states?

Solution Approach

The implementation of the solution makes use of array manipulation techniques to efficiently track the lengths of contiguous groups of 1s as the binary string gets updated.

Here's a step-by-step breakdown of the Reference Solution Approach provided in Python:

  1. The problem is first simplified by handling the special case where m is equal to n. If this is the case, we return n since the only possible group of length m will be formed at the last step.

  2. The cnt array of length n + 2 is initialized with zeros to keep track of the lengths of contiguous groups of 1s. Extra elements are added to the bounds to avoid index out of bounds errors when checking neighbors.

  3. We iterate over the arr using a loop: for i, v in enumerate(arr):. In each iteration, v represents the position in the binary string from the permutation where we turn a 0 into a 1.

  4. Since arr is 1-indexed and Python arrays are 0-indexed, we adjust by decrementing v by one (v -= 1).

  5. We retrieve the lengths of the groups on the left l = cnt[v - 1] and on the right r = cnt[v + 1] of the current position.

  6. We check if the current setting of the bit creates or destroys a group of ones with the length equal to m. If either the left or right contiguous group size equals m, we update the answer with the current step ans = i since it could be the latest step at which there exists a group of ones of length m.

  7. The lengths of the contiguous groups that are updated as a result of the current operation are then set at both ends of the new group by updating cnt[v - l] and cnt[v + r].

  8. The length of the new group is the sum of lengths of the left and right groups plus one for the current position (l + r + 1).

  9. We continue this process until all elements in arr have been processed.

  10. Finally, the variable ans holds the latest step at which a group of 1s of length exactly m was created, and it is returned. If no such group was created, ans will remain as its initialized value -1, which is correctly returned.

By using an array to keep track of the lengths of groups and updating this as we perform each operation, we maintain a running record of the state of the binary string throughout the process, enabling us to identify the correct step at which the condition is met.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example Walkthrough

Let's demonstrate the solution approach with an example. Suppose arr = [3, 5, 1, 2, 4] and m = 1. The binary string starts as 00000 and n = 5.

To aid our understanding, we'll be tracking the binary string, the cnt array, and which step we encounter a contiguous group of 1s of length m.

  1. Since m is not equal to n, we proceed with the solution and initialize cnt as [0, 0, 0, 0, 0, 0, 0]. This extra padding helps avoid out-of-bounds errors.

  2. In the first step, we turn the 3rd bit of the binary string to 1, which is at index 2 in 0-based indexing. The binary string becomes 00100. Here, the left group l is 0, and the right group r is also 0. Since there are no contiguous groups of 1s, we just set the cnt array at indices [2] to 1.

    Binary string: 00100

    cnt array: [0, 0, 1, 0, 0, 0, 0]

  3. In the second step, we set the 5th bit to 1: 00101. The left group on 5th position is 0 and the right group is 0. We update the cnt at [4] to 1. Since a contiguous subsection of length 1 is formed, we set ans to the current step i which is 2.

    Binary string: 00101

    cnt array: [0, 0, 1, 0, 1, 0, 0]

    ans = 2

  4. For the third step, we update the 1st bit: 10101. The left group l is 0 and the right group r is 0. Update cnt at [0] to 1. Since a contiguous subsection of length 1 is formed, we update ans to 3.

    Binary string: 10101

    cnt array: [1, 0, 1, 0, 1, 0, 0]

    ans = 3

  5. In the fourth step, setting the 2nd bit to 1 updates the binary string to 11101. The left group l is 1, and the right group r is 1. We update cnt at [2] and cnt at [0] to 1 + 1 + 1 = 3 since now they're part of a larger group. After this change, there's no group of length 1, so ans is not updated.

    Binary string: 11101

    cnt array: [3, 0, 3, 0, 1, 0, 0]

  6. In the final step, we set the 4th bit to 1: 11111. The left group l is 3, and the right group r is 1. We update cnt at [0] and cnt at [4] to 3 + 1 + 1 = 5. There's no longer a group of length 1, so ans remains the same.

    Binary string: 11111

    cnt array: [5, 0, 3, 0, 5, 0, 0]

  7. Since we have processed all elements in arr, and we did not encounter a new group of 1s of length m since step 3, ans remains as 3.

Therefore, the latest step at which a contiguous group of 1s of length exactly m was created is step 3, which is the returned result of this example problem.

Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Python Solution

1class Solution:    
2    def findLatestStep(self, arr: List[int], length_m: int) -> int:
3        # Length of the array 'arr' which represents the positions filled
4        total_length = len(arr)
5
6        # Situation where each step fills a unique position, resulting in 'm' as the total length
7        if length_m == total_length:
8            return total_length
9
10        # Initialize an array to keep track of continuous segment lengths around each position
11        # Extra two slots for padding the left and right ends to simplify boundary conditions
12        count = [0] * (total_length + 2)
13      
14        # Variable to keep track of the latest step where there is at least one segment of length 'm'
15        latest_step = -1
16      
17        # Iterate over the array 'arr', 'pos' holds the position to be filled during each step
18        for step, pos in enumerate(arr):
19            # Adjust 'pos' to be zero-indexed
20            pos -= 1
21          
22            # Retrieve lengths of segments directly left (l) and right (r) of the current position
23            left_segment, right_segment = count[pos - 1], count[pos + 1]
24          
25            # Check if either segment adjacent to the filled position is exactly of length 'm'
26            if left_segment == length_m or right_segment == length_m:
27                latest_step = step  # Record the latest valid step
28
29            # Update the border values of the segment including the new position 'pos'
30            # The new segment length is the sum of left, right segments plus the new position itself
31            count[pos - left_segment] = count[pos + right_segment] = left_segment + right_segment + 1
32      
33        # Return the latest step where a continuous segment of length 'm' occurred
34        return latest_step
35
36# Example usage:
37# result = Solution().findLatestStep([3, 5, 1, 2, 4], 1)
38# Assuming the List type is imported from typing, this would return 4, since the latest step
39# where a length of 1 is left occurs at step 4 (zero-indexed, would be position 5 in one-indexed)
40

Java Solution

1class Solution {
2    // Method to find the latest step where there are exactly 'm' continuous blocks that are filled
3    public int findLatestStep(int[] arr, int m) {
4        int n = arr.length;
5        // If 'm' is equal to the length of the array, the answer is the length since all will be filled continuously last
6        if (m == n) {
7            return n;
8        }
9      
10        // Initialize the count array to track the number of continuous filled blocks
11        // Extra space is allocated for boundaries to avoid IndexOutOfBoundException
12        int[] count = new int[n + 2];
13        int answer = -1; // Initialize the answer as -1, assuming no such step is found
14      
15        // Iterate through the array to simulate the filling process
16        for (int i = 0; i < n; ++i) {
17            int currentValue = arr[i]; // Get the current position to fill
18            // Retrieve length of continuous blocks to the left and right
19            int left = count[currentValue - 1];
20            int right = count[currentValue + 1];
21          
22            // If either side has exactly 'm' filled blocks, update the answer to the current step
23            if (left == m || right == m) {
24                answer = i;
25            }
26          
27            // Update the count of the new continuous block (after merging with adjacent filled blocks if any)
28            // We update the beginning and end of the continuous block
29            count[currentValue - left] = left + right + 1;
30            count[currentValue + right] = left + right + 1;
31        }
32        // Return the step number where we last saw 'm' continuous blocks filled
33        return answer;
34    }
35}
36

C++ Solution

1class Solution {
2public:
3    // Function that finds the last step number where there is a group with m consecutive '1's after 
4    // turning the bits one by one from the 'arr' array on a binary string of all '0's.
5    int findLatestStep(vector<int>& arr, int m) {
6        int n = arr.size();
7        // Immediately return the size of the array if m equals the array size since the last step
8        // would turn the entire string into '1's which is a group of m consecutive '1's.
9        if (m == n) 
10            return n;
11
12        // Initialize a count array to keep track of lengths of consecutive '1's with
13        // two extra elements for handling edge cases (prevent out of bounds access).
14        vector<int> lengthAtEdges(n + 2, 0);
15
16        // Variable to store the answer, start with -1 to signify not found.
17        int latestStep = -1;
18
19        // Iterate over the input array to simulate flipping the bits.
20        for (int step = 0; step < n; ++step) {
21            // Get the current position to flip from the array.
22            int positionToFlip = arr[step];
23
24            // Find the lengths of consecutive '1's to the left and right of the position.
25            int leftConsecutiveLength = lengthAtEdges[positionToFlip - 1];
26            int rightConsecutiveLength = lengthAtEdges[positionToFlip + 1];
27
28            // If flipping this bit completes a group of size m, then set 'latestStep' to
29            // the current step (1-indexed as per the problem statement).
30            // Since 'step' starts from 0, we need to add 1 to align with the problem statement.
31            if (leftConsecutiveLength == m || rightConsecutiveLength == m)
32                latestStep = step + 1;
33
34            // Update the length at the edges of the group formed by flipping the current bit.
35            // The total length of the new group is the sum of the left and right lengths, plus 1
36            // for the flipped bit itself.
37            lengthAtEdges[positionToFlip - leftConsecutiveLength] = 
38            lengthAtEdges[positionToFlip + rightConsecutiveLength] = 
39                leftConsecutiveLength + rightConsecutiveLength + 1;
40        }
41
42        // Return the latest step at which there was a group of m consecutive '1's.
43        return latestStep;
44    }
45};
46

Typescript Solution

1// Size of the array
2let arraySize: number;
3
4// Array to track lengths of consecutive '1's at the edges
5let lengthAtEdges: number[];
6
7// Initialize the variables necessary for storing the state of the solution.
8function initialize(n: number) {
9    arraySize = n;
10    lengthAtEdges = Array(n + 2).fill(0);
11}
12
13// Function that simulates flipping the bits at each step and finds 
14// the last step number where there is a group with exactly m 
15// consecutive '1's after flipping the bits.
16function findLatestStep(arr: number[], m: number): number {
17    initialize(arr.length);
18
19    // Special case: if m equals the array size, return the size of 
20    // the array since in the last step the entire string will be '1's.
21    if (m === arraySize) {
22        return arraySize;
23    }
24
25    // Variable to store the answer; initialized to -1 to signify not found
26    let latestStep: number = -1;
27
28    // Iterate over the array to simulate flipping the bits
29    for (let step = 0; step < arraySize; ++step) {
30        let positionToFlip: number = arr[step];
31
32        // Find the lengths of consecutive '1's to the left and right
33        let leftConsecutiveLength: number = lengthAtEdges[positionToFlip - 1];
34        let rightConsecutiveLength: number = lengthAtEdges[positionToFlip + 1];
35      
36        // Check if flipping this bit completes a group of size m
37        if (leftConsecutiveLength === m || rightConsecutiveLength === m) {
38            latestStep = step + 1;
39        }
40      
41        // Update the length at the edges of the group formed by
42        // flipping the current bit including flipped bit itself
43        let newGroupLength: number = leftConsecutiveLength + rightConsecutiveLength + 1;
44        lengthAtEdges[positionToFlip - leftConsecutiveLength] = newGroupLength;
45        lengthAtEdges[positionToFlip + rightConsecutiveLength] = newGroupLength;
46    }
47
48    // Return the latest step with a group of m consecutive '1's
49    return latestStep;
50}
51
Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Time and Space Complexity

The given Python code aims to solve a problem by tracking lengths of segments of '1's in a binary array, which is initially all '0's. Each element in arr represents the position being flipped from '0' to '1'. The code returns the last step (i) where there exists a segment with exactly m '1's.

Time Complexity

The primary operation in this loop is accessing and modifying elements in the cnt list, which takes constant time O(1) for each access or modification.

The for-loop runs for each element in arr, which means it iterates n times, where n is the length of arr. Inside this loop, there are constant-time operations being done. Therefore, the overall time complexity of the code is O(n).

Space Complexity

The space complexity is determined by the additional space used by the algorithm aside from the input. In this code, the dominant extra space is used by the cnt array, which has a length of n + 2. Hence, space complexity is also O(n).

To summarize, the algorithm has a time complexity of O(n) and a space complexity of O(n).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫