1375. Number of Times Binary String Is Prefix-Aligned

Problem Link

Description

---

You have a 1-indexed binary string of length n where all the bits are 0 initially. We will flip all the bits of this binary string (i.e., change them from 0 to 1) one by one. You are given a 1-indexed integer array flips where flips[i] indicates that the bit at index i will be flipped in the ith step.

A binary string is prefix-aligned if, after the ith step, all the bits in the inclusive range [1, i] are ones and all the other bits are zeros.

Return the number of times the binary string is prefix-aligned during the flipping process.

 

Example 1:

Input: flips = [3,2,4,1,5]
Output: 2
Explanation: The binary string is initially "00000".
After applying step 1: The string becomes "00100", which is not prefix-aligned.
After applying step 2: The string becomes "01100", which is not prefix-aligned.
After applying step 3: The string becomes "01110", which is not prefix-aligned.
After applying step 4: The string becomes "11110", which is prefix-aligned.
After applying step 5: The string becomes "11111", which is prefix-aligned.
We can see that the string was prefix-aligned 2 times, so we return 2.

Example 2:

Input: flips = [4,1,2,3]
Output: 1
Explanation: The binary string is initially "0000".
After applying step 1: The string becomes "0001", which is not prefix-aligned.
After applying step 2: The string becomes "1001", which is not prefix-aligned.
After applying step 3: The string becomes "1101", which is not prefix-aligned.
After applying step 4: The string becomes "1111", which is prefix-aligned.
We can see that the string was prefix-aligned 1 time, so we return 1.

 

Constraints:

• n == flips.length
• 1 <= n <= 5 * 104
• flips is a permutation of the integers in the range [1, n].

Solution

---

C++

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int right = 0, res = 0;
 
        for (int i = 0; i < light.size(); i++){
            right = max(right, light[i]);
            res += (right == i + 1);
        }
        
        return res;
    }
};

Python3

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        n = len(light)
        blues = [False] * n
        ons = [False] * n
        res = 0
        on = 0
        for i, x in enumerate(light):
            ons[x-1] = True
            # if idx == 0, then light it up to blue
            if x == 1 or blues[x-2]: 
                blues[x-1] = True
 
            r = x
            if blues[x-1]:
                while r < n and ons[r]:
                    blues[r] = True
                    on -= 1
                    r += 1
            else:
                on += 1
            
            if on == 0:
                res += 1
            
        return res