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 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 isprefix-aligned during the flipping process.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7
8

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^4
  • flips is a permutation of the integers in the range [1, n].

Solution

Method 1 – Track Maximum Flipped Position

Intuition

If after i steps, the maximum flipped position is i, then all positions 1..i have been flipped, so the prefix is aligned. We can track the max position after each step and count how many times max == i.

Approach

  1. Initialize max_pos = 0, ans = 0.
  2. For each step i (1-based), update max_pos = max(max_pos, flips[i-1]).
  3. If max_pos == i, increment ans.
  4. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

func numTimesAllBlue(flips []int) int {
    ans, maxPos := 0, 0
    for i, f := range flips {
        if f > maxPos { maxPos = f }
        if maxPos == i+1 { ans++ }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

class Solution {
    fun numTimesAllBlue(flips: IntArray): Int {
        var ans = 0
        var maxPos = 0
        for (i in flips.indices) {
            maxPos = maxOf(maxPos, flips[i])
            if (maxPos == i+1) ans++
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def numTimesAllBlue(self, flips: list[int]) -> int:
        ans = max_pos = 0
        for i, f in enumerate(flips):
            max_pos = max(max_pos, f)
            if max_pos == i+1:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn num_times_all_blue(flips: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut max_pos = 0;
        for (i, &f) in flips.iter().enumerate() {
            max_pos = max_pos.max(f as usize);
            if max_pos == i+1 { ans += 1; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)