{x}
blog image

Number of Times Binary String Is Prefix-Aligned

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 Explanation:

This problem asks to find the number of times the binary string becomes prefix-aligned during a sequence of bit flips. A prefix-aligned string means all bits up to a certain point are 1, and the rest are 0. The most efficient way to solve this is by tracking the maximum index flipped so far.

Algorithm:

  1. Initialization:

    • ans: Counts the number of times the string is prefix-aligned (initialized to 0).
    • mx: Keeps track of the maximum index flipped so far (initialized to 0).

  2. Iteration:

    • Iterate through the flips array.
    • For each element x (representing the index flipped at the current step), update mx to be the maximum of mx and x. This ensures mx always holds the highest index flipped up to the current step.
    • If mx is equal to the current iteration index i, it means all bits from 1 to i have been flipped to 1. This indicates a prefix-aligned string, so increment ans.

  3. Return:

    • After iterating through all flips, return ans.

Time Complexity: O(n), where n is the length of the flips array. We iterate through the array once.

Space Complexity: O(1). We use only a few constant extra variables.

Code in Different Languages:

The code implementations below follow the algorithm described above. They differ slightly in syntax but share the same core logic.

Python3:

class Solution:
    def numTimesAllBlue(self, flips: List[int]) -> int:
        ans = mx = 0
        for i, x in enumerate(flips, 1):
            mx = max(mx, x)
            ans += mx == i
        return ans

Java:

class Solution {
    public int numTimesAllBlue(int[] flips) {
        int ans = 0, mx = 0;
        for (int i = 1; i <= flips.length; ++i) {
            mx = Math.max(mx, flips[i - 1]);
            if (mx == i) {
                ++ans;
            }
        }
        return ans;
    }
}

C++:

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

Go:

func numTimesAllBlue(flips []int) (ans int) {
	mx := 0
	for i, x := range flips {
		mx = max(mx, x)
		if mx == i+1 {
			ans++
		}
	}
	return
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

TypeScript:

function numTimesAllBlue(flips: number[]): number {
    let ans = 0;
    let mx = 0;
    for (let i = 1; i <= flips.length; ++i) {
        mx = Math.max(mx, flips[i - 1]);
        if (mx === i) {
            ++ans;
        }
    }
    return ans;
}

All these code snippets achieve the same result with the same time and space complexity. The choice of language depends on personal preference and project requirements.