Problem Description

You start with a binary string of length n where all bits are initially 0. The string uses 1-based indexing (positions are numbered from 1 to n).

You're given an array flips that tells you the order in which to flip bits from 0 to 1. Specifically, flips[i] indicates which bit position to flip in the i-th step.

A binary string is considered prefix-aligned at step i if:

• All bits from position 1 to position i are 1
• All bits from position i+1 to position n are 0

Your task is to count how many times the binary string becomes prefix-aligned during the entire flipping process.

Example walkthrough:

If flips = [3, 2, 4, 1, 5] and n = 5:

• Step 1: Flip bit 3 → String is 00100 (not prefix-aligned)
• Step 2: Flip bit 2 → String is 01100 (not prefix-aligned)
• Step 3: Flip bit 4 → String is 01110 (not prefix-aligned)
• Step 4: Flip bit 1 → String is 11110 (prefix-aligned! First 4 bits are 1)
• Step 5: Flip bit 5 → String is 11111 (prefix-aligned! All 5 bits are 1)

The answer would be 2 since the string was prefix-aligned after steps 4 and 5.

The solution works by tracking the maximum bit position flipped so far. When this maximum equals the current step number i, it means all positions from 1 to i have been flipped, making the string prefix-aligned at that moment.

Intuition

The key insight is recognizing what it means for a binary string to be prefix-aligned after exactly i steps.

For the string to be prefix-aligned after step i, we need all positions from 1 to i to be flipped to 1, while positions beyond i remain 0. This means we must have flipped exactly the positions {1, 2, 3, ..., i} in some order during the first i steps.

Think about it this way: if we've completed i steps and the maximum position we've flipped so far is greater than i, then position i+1 or higher has already been flipped to 1, so the string cannot be prefix-aligned. Conversely, if the maximum position is less than i, then we haven't yet flipped all positions up to i, so again it's not prefix-aligned.

The string is prefix-aligned after step i if and only if the maximum position flipped in the first i steps equals exactly i. This happens when we've flipped all and only the positions {1, 2, ..., i}.

For example, if after 3 steps we've flipped positions [2, 1, 3], the maximum is 3, which equals the step count, so it's prefix-aligned. But if we've flipped [2, 1, 5], the maximum is 5, which is greater than 3, so it's not prefix-aligned because position 5 is already 1 while position 3 is still 0.

This observation leads to the elegant solution: track the maximum position flipped so far (mx), and whenever mx == i, we have a prefix-aligned state.

Solution Approach

The implementation uses a simple traversal with a running maximum tracker:

1. Initialize variables:

   • ans to count prefix-aligned occurrences (starts at 0)
   • mx to track the maximum position flipped so far (starts at 0)

2. Traverse the flips array with enumeration:

   • Use enumerate(flips, 1) to get both the step number i (1-indexed) and the position to flip x
   • This makes i represent which step we're on (1st step, 2nd step, etc.)

3. For each step:

   • Update the maximum: mx = max(mx, x) where x is the current position being flipped
   • Check if prefix-aligned: if mx == i, increment the answer counter
   • The condition mx == i is converted to a boolean (True = 1, False = 0) and added directly: ans += mx == i

4. Return the final count after processing all flips

Why this works:

• At step i, if the maximum position flipped equals i, it means:
  • We've flipped at least one bit at position i (since mx >= i)
  • We haven't flipped any bit beyond position i (since mx <= i)
  • Combined with the fact that we've made exactly i flips, this guarantees we've flipped all positions from 1 to i exactly once

Time Complexity: O(n) where n is the length of the flips array - single pass through the array

Space Complexity: O(1) - only using two variables regardless of input size

Example Walkthrough

Let's trace through a small example with flips = [2, 1, 3]:

Initial state: Binary string is 000 (all positions start as 0)

Step 1: Flip position 2

• Current string becomes: 010
• Maximum position flipped so far: mx = 2
• Current step number: i = 1
• Is mx == i? No (2 ≠ 1), so NOT prefix-aligned
• The string would need to be 100 to be prefix-aligned at step 1

Step 2: Flip position 1

• Current string becomes: 110
• Update maximum: mx = max(2, 1) = 2
• Current step number: i = 2
• Is mx == i? Yes (2 == 2), so IS prefix-aligned! ✓
• Indeed, positions 1-2 are all 1, and position 3 is 0

Step 3: Flip position 3

• Current string becomes: 111
• Update maximum: mx = max(2, 3) = 3
• Current step number: i = 3
• Is mx == i? Yes (3 == 3), so IS prefix-aligned! ✓
• All positions 1-3 are 1 (the entire string)

Result: The string was prefix-aligned 2 times (after steps 2 and 3)

The key insight: When mx == i, it means we've flipped exactly the positions {1, 2, ..., i} in some order, creating a perfect prefix of ones.

Solution Implementation

Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the length of the array flips. This is because the code iterates through the array exactly once using a single for loop with enumerate(). Within each iteration, it performs constant-time operations: finding the maximum between two numbers (max(mx, x)), comparing two values (mx == i), and incrementing a counter. Since these operations take O(1) time and are executed n times, the overall time complexity is O(n).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. It maintains three variables: ans (counter for valid moments), mx (maximum value seen so far), and the loop variables i and x. These variables require constant space that doesn't grow with the input size n, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusion Between 0-Based and 1-Based Indexing

One of the most common mistakes is mixing up the indexing systems. The problem uses 1-based indexing for bit positions, but Python arrays use 0-based indexing.

Incorrect approach:

# Wrong: treating step number as 0-based
for i, x in enumerate(flips):  # i starts from 0
    mx = max(mx, x)
    if mx == i:  # This will never match correctly!
        ans += 1

Why it fails: When checking mx == i, we're comparing a 1-based position value with a 0-based step counter. For example, after the first flip of position 1, mx would be 1 but i would be 0.

Correct solution:

# Use enumerate with start=1 to align step numbers with position values
for i, x in enumerate(flips, 1):  # i starts from 1
    mx = max(mx, x)
    if mx == i:  # Now both use the same numbering system
        ans += 1

2. Misunderstanding the Prefix-Aligned Condition

Another pitfall is incorrectly determining when the string is prefix-aligned by checking individual bits or maintaining the actual binary string.

Incorrect approach:

# Wrong: trying to maintain the actual binary string
binary = [0] * n
for i, pos in enumerate(flips, 1):
    binary[pos-1] = 1  # Flip the bit
    # Check if first i bits are 1 and rest are 0
    if all(binary[j] == 1 for j in range(i)) and \
       all(binary[j] == 0 for j in range(i, n)):
        ans += 1

Why it's inefficient: This approach has O(n²) time complexity and unnecessarily maintains the entire binary string state.

Correct insight: We only need to track the maximum position flipped. If after i steps the maximum position is exactly i, then positions 1 through i must all be flipped (since we made i distinct flips and none went beyond position i).

3. Off-by-One Errors When Manually Indexing

When not using enumerate(flips, 1), developers might manually track the step number and make off-by-one errors.

Incorrect approach:

# Wrong: manual indexing with incorrect step counting
mx = 0
ans = 0
for i in range(len(flips)):
    mx = max(mx, flips[i])
    if mx == i:  # Wrong! i is 0-based but mx contains 1-based values
        ans += 1

Correct alternative (if not using enumerate):

mx = 0
ans = 0
for i in range(len(flips)):
    mx = max(mx, flips[i])
    if mx == i + 1:  # Adjust i to be 1-based
        ans += 1