# Number of Times Binary String Is Prefix-Aligned
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-times-binary-string-is-prefix-aligned)
Canonical: https://scaleengineer.com/dsa/problems/number-of-times-binary-string-is-prefix-aligned
**Data structures:** Array
---
## Problem
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 `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]`.

# Approaches
## Brute-force Simulation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int numTimesAllBlue(int[] flips) {
        int n = flips.length;
        boolean[] bits = new boolean[n + 1];
        int count = 0;
        for (int i = 0; i < n; i++) {
            int step = i + 1;
            int pos = flips[i];
            bits[pos] = true;

            boolean isAligned = true;
            for (int j = 1; j <= step; j++) {
                if (!bits[j]) {
                    isAligned = false;
                    break;
                }
            }

            if (isAligned) {
                count++;
            }
        }
        return count;
    }
}
```
### 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`.

## Optimal Approach: Tracking Maximum Flipped Position
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`.
**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`.
**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.
### Explanation
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.

```java
class Solution {
    public int numTimesAllBlue(int[] flips) {
        int n = flips.length;
        int count = 0;
        int rightmostOne = 0; // Tracks the maximum position flipped so far
        for (int i = 0; i < n; i++) {
            // Update the rightmost position that has been flipped to 1
            rightmostOne = Math.max(rightmostOne, flips[i]);
            
            // The number of flips done so far is i + 1.
            // If the rightmost '1' is at position i + 1, it means
            // all positions from 1 to i + 1 have been flipped.
            if (rightmostOne == i + 1) {
                count++;
            }
        }
        return count;
    }
}
```
### 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`.

# Solutions
### Java

```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;
  }
}

```

### Python

```python
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

```

### CPP

```cpp
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;
  }
};

```