Leetcode 1562. Find Latest Group of Size M

Problem Explanation:

The given problem presents you with an array arr that represents a permutation of numbers from 1 to n and a binary string of size n initially having all its bits set to zero. The challenge is to find the latest step at which there exists a group of ones of length m in the binary string after performing certain operations steps on the string.

The operations steps are as follows:

• At each ith step (where i ranges from 1 to n), the bit at position arr[i] in the binary string is set to 1.
• A group of ones is defined as a contiguous substring of 1s in the binary string such that it cannot be extended in either direction.
• After each step, we check for the existence of a group of ones of length m.

If there exists such a group, we need to return the latest step at which it existed. If no such group exists, we return -1.

For example, consider the input arr = [3,5,1,2,4], m = 1. After each step, the binary string and the groups formed are as follows:

• 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"]

As per this example, the latest step at which there exists a group of size 1 is step 4.

The given constraints for the problem as as follows:

• The length of the array is n, where 1 <= n <= 10^5
• All of arr[i] are distinct, where 1 <= arr[i] <= n
• 1 <= m <= the length of arr

Approach:

We can maintain an array sizes[] that stores the size of the group starting from i or ending at i (based on 1-indexing). If we encounter a group of ones of size m in a step, we store that as the possible answer.

The solution idea is to update the sizes[] array in each step, while checking if there is a group of length m in the previous step, if it is, we record the step, every group begins and ends in sizes[] array are recorded it's length, after we set arr[i] to 1, the group it belongs will be merged and we have to update the begin and end to the new length.

Python Solution

1
2python
3class Solution:
4    def findLatestStep(self, arr, m):
5        if len(arr) == m:
6            return len(arr)
7          
8        ans, step = -1, 0
9        sizes = [0] * (len(arr) + 2)
10
11        for i in arr:
12            step += 1
13            if sizes[i - 1] == m or sizes[i + 1] == m:
14                ans = step - 1
15            head = i - sizes[i - 1]
16            tail = i + sizes[i + 1]
17            sizes[head] = tail - head + 1
18            sizes[tail] = tail - head + 1
19               
20        return ans

Java Solution

1
2java
3class Solution {
4    public int findLatestStep(int[] arr, int m) {
5        if (arr.length == m)
6            return arr.length;
7      
8        int ans = -1, step = 0;
9        int[] sizes = new int[arr.length + 2];
10        
11        for (int i : arr) {
12            step += 1;
13            if (sizes[i-1] == m || sizes[i+1] == m)
14                ans = step - 1;
15            int head = i - sizes[i-1];
16            int tail = i + sizes[i+1];
17            sizes[head] = tail - head + 1;
18            sizes[tail] = tail - head + 1;
19        }
20            
21        return ans;
22    }
23}

JavaScript Solution

1
2javascript
3var findLatestStep = function(arr, m) {
4    if (arr.length == m)
5        return arr.length;
6
7    let ans = -1, step = 0;
8    let sizes = new Array(arr + 2).fill(0);
9    
10    for (const i of arr) {
11        step += 1;
12        if (sizes[i - 1] == m || sizes[i + 1] == m)
13            ans = step - 1;
14        let head = i - sizes[i - 1];
15        let tail = i + sizes[i + 1];
16        sizes[head] = tail - head + 1;
17        sizes[tail] = tail - head + 1;
18    }
19
20    return ans;
21};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int findLatestStep(vector<int>& arr, int m) {
6        if (arr.size() == m)
7            return arr.size();
8
9        int ans = -1, step = 0;
10        vector<int> sizes(arr.size() + 2);
11
12        for (const int i: arr) {
13            step++;
14            if (sizes[i - 1] == m || sizes[i + 1] == m)
15                ans = step - 1;
16            int head = i - sizes[i - 1];
17            int tail = i + sizes[i + 1];
18            sizes[head] = tail - head + 1;
19            sizes[tail] = tail - head + 1;
20        }
21
22        return ans;
23    }
24};

C# Solution

1
2csharp
3public class Solution {
4    public int FindLatestStep(int[] arr, int m) {
5        if (arr.Length == m)
6            return arr.Length;
7          
8        int ans = -1, step = 0;
9        int[] sizes = new int[arr.Length + 2];
10
11        foreach(int i in arr) {
12            step += 1;
13            if (sizes[i-1] == m || sizes[i+1] == m)
14                ans = step - 1;
15            int head = i - sizes[i-1];
16            int tail = i + sizes[i+1];
17            sizes[head] = tail - head + 1;
18            sizes[tail] = tail - head + 1;
19        }
20            
21        return ans;
22    }
23}

As you can see from the solutions, by keeping a track of the sizes of groups of ones obtained at each step, we can efficiently solve the problem. The complexity of this solution is O(n), given the length of the array and storing the size for each operation we have to perform.## PHP Solution

The PHP solution involves implementing the same logic as described above with minor syntactical differences. Here is the PHP solution:

1
2php
3class Solution {
4    function findLatestStep($arr, $m) {
5        if (count($arr) == $m)
6            return count($arr);
7
8        $ans = -1;
9        $step = 0;
10        $sizes = array_fill(0, count($arr) + 2, 0);
11
12        foreach ($arr as $i) {
13            $step++;
14            if ($sizes[$i - 1] == $m || $sizes[$i + 1] == $m)
15                $ans = $step - 1;
16            $head = $i - $sizes[$i - 1];
17            $tail = $i + $sizes[$i + 1];
18            $sizes[$head] = $tail - $head + 1;
19            $sizes[$tail] = $tail - $head + 1;
20        }
21
22        return $ans;
23    }
24}

Scala Solution

The Scala solution is similar to the Java solution, with the difference that Scala supports functional programming which allows us to reason about problems in a different way.

1
2scala
3object Solution {
4    def findLatestStep(arr: Array[Int], m: Int): Int = {
5        if (arr.length == m)
6            return arr.length
7
8        var ans = -1
9        var step = 0
10        var sizes = Array.fill[Int](arr.length + 2)(0)
11
12        for (i <- arr) {
13            step += 1
14            if (sizes(i - 1) == m || sizes(i + 1) == m)
15                ans = step - 1;
16            val head = i - sizes(i - 1)
17            val tail = i + sizes(i + 1)
18            sizes(head) = tail - head + 1
19            sizes(tail) = tail - head + 1
20        }
21        
22        ans
23    }
24}

Rust Solution

Finally, here is the solution in Rust, a statically typed compiled language designed for performance and safety, especially safe concurrency.

1
2rust
3impl Solution {
4    pub fn find_latest_step(arr: Vec<i32>, m: i32) -> i32 {
5        let n = arr.len();
6        if n == m as usize { return n as i32; }
7        
8        let mut ans = -1;
9        let mut step = 0;
10        let mut sizes = vec![0; n+2];
11
12        for i in &arr {
13            step += 1;
14            let i = *i as usize;
15            if sizes[i - 1] == m || sizes[i + 1] == m {
16                ans = step as i32 - 1;
17            }
18            let head = i - sizes[i - 1];
19            let tail = i + sizes[i + 1];
20            sizes[head] = tail + 1 - head;
21            sizes[tail] = tail + 1 - head;
22        }
23        
24        ans
25    }
26}

By keeping a track of the sizes of groups of ones at each step in binary string, we are able to solve the problem in an efficient way. The time and space complexity of each solution is O(n), which guarantees performance even for large inputs.