Problem Description

You are given an array flips of length n that represents a permutation of the numbers from 1 to n. Imagine you have a binary string of length n, initially all zeros. You perform n operations: in the i-th operation, you flip the bit at position flips[i] (1-based index) from 0 to 1.

After each flip, you check if all the bits in the prefix of the string (from position 1 to the current operation number) are set to 1. If so, you count this as a "prefix-aligned" moment.

Your task is to return the total number of times the binary string is prefix-aligned after performing all flips.

• Constraints:
  • Each number from 1 to n appears exactly once in flips (i.e., a permutation).
  • Bits are flipped from 0 to 1, never back to 0.
  • Check prefix alignment only after each operation.

Thought Process

At first glance, you might consider simulating the entire binary string and, after each flip, checking the prefix to see if all bits from position 1 to the current operation are set to 1. However, this would be inefficient, especially for large n, because checking the prefix at every step could take up to O(n^2) time.

To optimize, let's ask: What does it mean for the prefix (up to the current operation) to be all 1s? It means that all numbers from 1 up to the current step have been flipped. If, after i flips, the largest number we've flipped is i, then all numbers from 1 to i must have been flipped (since they're unique and no duplicates).

So, instead of tracking the whole binary string, we can track the maximum position flipped so far and compare it to the operation number.

Solution Approach

• Initialize a variable max_flipped to 0. This will keep track of the highest position flipped so far.
• Initialize a counter count to 0 to count the number of prefix-aligned moments.
• Iterate through flips:
  • At each step i (0-based), flip the bit at flips[i].
  • Update max_flipped to be the maximum of its current value and flips[i].
  • If max_flipped == i + 1 (since i is 0-based), it means all positions from 1 to i+1 have been flipped, so increment count.
• Return count after finishing the iteration.

The insight is that we don't need to check the entire prefix; we just need to know if the largest flipped position matches the current step. If it does, then all smaller positions must have been flipped earlier.

Example Walkthrough

Let's use flips = [3,2,4,1,5] as a sample input.

• Step 1: Flip position 3. max_flipped = 3, i+1 = 1. Not equal, so not prefix-aligned.
• Step 2: Flip position 2. max_flipped = 3, i+1 = 2. Not equal.
• Step 3: Flip position 4. max_flipped = 4, i+1 = 3. Not equal.
• Step 4: Flip position 1. max_flipped = 4, i+1 = 4. Now, max_flipped == i+1, so we have a prefix-aligned moment. Increment count to 1.
• Step 5: Flip position 5. max_flipped = 5, i+1 = 5. Again, max_flipped == i+1, so increment count to 2.

The final answer is 2.

Code Implementation

class Solution:
    def numTimesAllBlue(self, flips):
        max_flipped = 0
        count = 0
        for i, flip in enumerate(flips):
            max_flipped = max(max_flipped, flip)
            if max_flipped == i + 1:
                count += 1
        return count
      

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

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

var numTimesAllBlue = function(flips) {
    let maxFlipped = 0, count = 0;
    for (let i = 0; i < flips.length; i++) {
        maxFlipped = Math.max(maxFlipped, flips[i]);
        if (maxFlipped === i + 1) {
            count++;
        }
    }
    return count;
};
      

Time and Space Complexity

• Brute-Force Approach:
  • For each operation, check the entire prefix for all 1s. This takes O(n) time per operation, for a total of O(n^2) time.
  • Space complexity is O(n) to store the binary string.
• Optimized Approach (Current Solution):
  • Each flip is processed in O(1) time (just a max and comparison), so total time is O(n).
  • Space complexity is O(1), since only a few integer variables are used.

Summary

By recognizing that prefix alignment occurs only when the largest flipped position matches the number of operations so far, we avoid unnecessary checks and achieve an efficient O(n) solution. The key insight is that the permutation property guarantees all smaller positions are already flipped if the max matches the current index. This strategy makes the solution both simple and optimal.