Find Latest Group of Size M

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.

Solution

var findLatestStep = function(arr, m) {

const n = arr.length;

if (m === n) return n;

const length = new Array(n + 2).fill(0);

let count = 0;

let answer = -1;

for (let step = 0; step < n; step++) {

const pos = arr[step];

const left = length[pos - 1];

const right = length[pos + 1];

if (left === m) count--;

if (right === m) count--;

const newLength = left + right + 1;

length[pos - left] = newLength;

length[pos + right] = newLength;

length[pos] = newLength;

if (newLength === m) count++;

if (count > 0) {

answer = step + 1;

}

return answer;

};

Comments