Number of Times Binary String Is Prefix-Aligned

Med

#1275Time: O(n^2) - The outer loop runs `n` times, and for each iteration, the inner loop runs up to `n` times, leading to a quadratic time complexity.Space: O(n) - We use a boolean array of size `n+1` to store the state of the binary string.

Data structures

Array

Prompt

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 flips[i] will be flipped in the i^th step.

A binary string is prefix-aligned if, after the i^th 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 * 10⁴
flips is a permutation of the integers in the range [1, n].

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We maintain a representation of the binary string, flip the bits as instructed, and after each flip, we check the entire prefix of the current length to see if it's composed of all ones.

Algorithm

Initialize a boolean array bits of size n + 1 to all false to represent the binary string.
Initialize a counter count to 0.
Iterate through the flips array from i = 0 to n - 1.
- Let step = i + 1 be the current step number.
- Get the position to flip: pos = flips[i].
- Set bits[pos] to true.
- Check if the prefix [1, step] is aligned:
  - Assume it is aligned by setting a flag isAligned = true.
  - Start a nested loop from j = 1 to step.
  - If bits[j] is false, it means the prefix is not all ones. Set isAligned = false and break the inner loop.
- If isAligned remains true after the inner loop, increment count.
Return count.

Walkthrough

In this method, we use a boolean array, say bits, of size n + 1 (to handle 1-based indexing easily) to represent the binary string. This array is initialized to all false, corresponding to the initial string of all zeros. We then iterate through the flips array. For each step i (from 0 to n-1), we perform the (i+1)-th flip by setting bits[flips[i]] to true. After each flip, we must check if the string has become prefix-aligned. A string is prefix-aligned after k = i + 1 steps if all bits from 1 to k are true. To verify this, we use a nested loop that iterates from j = 1 to k, checking if bits[j] is true. If we find any bit in this range that is false, the condition is not met. If the entire prefix [1, k] consists of true values, we increment a counter. Finally, this counter gives the total number of times the string was prefix-aligned.

1class Solution {2    public int numTimesAllBlue(int[] flips) {3        int n = flips.length;4        boolean[] bits = new boolean[n + 1];5        int count = 0;6        for (int i = 0; i < n; i++) {7            int step = i + 1;8            int pos = flips[i];9            bits[pos] = true;10 11            boolean isAligned = true;12            for (int j = 1; j <= step; j++) {13                if (!bits[j]) {14                    isAligned = false;15                    break;16                }17            }18 19            if (isAligned) {20                count++;21            }22        }23        return count;24    }25}

Complexity

Time

O(n^2) - The outer loop runs `n` times, and for each iteration, the inner loop runs up to `n` times, leading to a quadratic time complexity.

Space

O(n) - We use a boolean array of size `n+1` to store the state of the binary string.

Trade-offs

Pros

Straightforward to implement as it directly models the problem statement.
Easy to understand and reason about.

Cons

Inefficient due to its O(n^2) time complexity.
Likely to result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger input sizes.

A more efficient approach is to find a simpler condition to check for a prefix-aligned state. After k steps, exactly k bits have been flipped to 1. The string is prefix-aligned if and only if the set of flipped positions is exactly {1, 2, ..., k}. This is equivalent to checking if the rightmost (or maximum) position flipped so far is exactly k.

Algorithm

Initialize a counter count to 0.
Initialize a variable rightmostOne to 0, which will track the maximum position flipped so far.
Iterate through the flips array from i = 0 to n - 1.
- Let step = i + 1 be the number of flips performed.
- Update rightmostOne by taking the maximum of its current value and the new flip position: rightmostOne = max(rightmostOne, flips[i]).
- Check if rightmostOne is equal to step.
- If rightmostOne == step, it means the prefix of length step is full. Increment count.
Return count.

Walkthrough

This optimal approach is based on a key observation. For the binary string to be prefix-aligned after k steps, two conditions must be met: 1) exactly k bits are '1', and 2) these '1's are located at positions 1, 2, ..., k. The problem statement guarantees that after k steps (processing flips[0] to flips[k-1]), exactly k unique bits have been flipped. So, we only need to ensure they are the correct ones. This is true if and only if the largest index flipped so far is exactly k.

Why? If the largest index flipped is m > k, then a bit outside the prefix [1, k] is '1', so it's not prefix-aligned. If the largest index flipped is m < k, it's impossible to have flipped k distinct bits since they would all have to be in the range [1, m]. Therefore, the only possibility for a prefix-aligned state is when the maximum flipped index equals the number of flips performed.

We can implement this by iterating through the flips array once. We maintain a variable, rightmostOne, to keep track of the maximum position flipped. At each step i, we update rightmostOne and check if it equals i + 1. If it does, we increment our count.

1class Solution {2    public int numTimesAllBlue(int[] flips) {3        int n = flips.length;4        int count = 0;5        int rightmostOne = 0; // Tracks the maximum position flipped so far6        for (int i = 0; i < n; i++) {7            // Update the rightmost position that has been flipped to 18            rightmostOne = Math.max(rightmostOne, flips[i]);9            10            // The number of flips done so far is i + 1.11            // If the rightmost '1' is at position i + 1, it means12            // all positions from 1 to i + 1 have been flipped.13            if (rightmostOne == i + 1) {14                count++;15            }16        }17        return count;18    }19}

Complexity

Time

O(n) - We iterate through the `flips` array only once, performing constant time operations in each iteration.

Space

O(1) - We only use a few variables to store the count and the maximum position, which does not depend on the input size `n`.

Trade-offs

Pros

Extremely efficient with linear time complexity.
Requires only constant extra space, making it optimal in terms of memory usage.
Passes for all constraints.

Cons

The logic is slightly more abstract and requires an insight into the problem's underlying structure, making it less obvious than the brute-force approach.

Solutions

Solution

1class Solution {2public3  int numTimesAllBlue(int[] flips) {4    int ans = 0, mx = 0;5    for (int i = 1; i <= flips.length; ++i) {6      mx = Math.max(mx, flips[i - 1]);7      if (mx == i) {8        ++ans;9      }10    }11    return ans;12  }13}

1class Solution:2    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

1class Solution {2public:3  int numTimesAllBlue(vector<int> &flips) {4    int ans = 0, mx = 0;5    for (int i = 1; i <= flips.size(); ++i) {6      mx = max(mx, flips[i - 1]);7      ans += mx == i;8    }9    return ans;10  }11};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem