Number of Times Binary String Is Prefix-Aligned: Max Tracking Pattern

You have a binary string of length n where every bit starts as 0. You are given an array flips where flips[i] is a 1-indexed position. At step i (1-indexed), you flip the bit at position flips[i] from 0 to 1. A binary string is prefix-aligned at step i if all bits from position 1 to position i are 1, and all remaining bits are 0. Return the number of steps where the binary string is prefix-aligned.

This is LeetCode 1375: Number of Times Binary String Is Prefix-Aligned, and it is a clean example of how tracking a running maximum can replace what looks like an expensive check.

Why this problem matters

The brute force approach is tempting: after each flip, scan the string from position 1 up to the current step and check whether every bit is set. That works, but it runs in O(n^2) time. The real lesson here is recognizing that you do not need to check the entire prefix at each step.

This problem teaches a pattern that shows up whenever you need to determine if a set of values "covers" a contiguous range. Job scheduling, task assignment, interval coverage, and array rearrangement problems all share this same structure. If you can track the maximum value you have seen so far, you can often avoid scanning the entire range.

Once you internalize this "running max equals expected boundary" pattern, you will spot it immediately in problems that ask whether a sequence of operations fills a contiguous range without gaps.

The key insight

At step i, you have flipped exactly i positions. For the prefix to be aligned, positions 1 through i must all be set to 1. Since every flips[i] value is unique (each position is flipped exactly once), the only way positions 1 through i are all filled is if the maximum position flipped so far equals i.

Think about it: if you have flipped i positions and the largest one is i, then the i flipped positions must be exactly {1, 2, 3, ..., i}. There is no room for gaps. Any gap would mean some position greater than i was flipped, pushing the max above i. And any missing position below i would mean some position above i was used instead, again pushing the max above i.

So the algorithm is:

1. Track the running maximum of all positions flipped so far.
2. At each step i, if the running maximum equals i, the prefix is aligned. Increment the count.
3. Return the count.

The solution

def numTimesAllBlue(flips: list[int]) -> int:
    max_pos = 0
    count = 0
    for i, pos in enumerate(flips, 1):
        max_pos = max(max_pos, pos)
        if max_pos == i:
            count += 1
    return count

Let's break down how this works.

The variable max_pos tracks the largest position that has been flipped so far. As we process each step, we update max_pos to be the larger of its current value and the newly flipped position.

The loop uses enumerate(flips, 1) so that i starts at 1, matching the 1-indexed step numbers in the problem. At each step, we compare max_pos to i. If they are equal, we know that all i flipped positions must be exactly the set {1, 2, ..., i}, which means the prefix is aligned.

The key reasoning is a counting argument: we have flipped exactly i distinct positions, and the largest is i. Since positions are in the range 1 to i and they are all distinct, they must be exactly 1, 2, 3, ..., i. No gaps are possible.

Visual walkthrough

Let's trace through flips = [3, 2, 4, 1, 5] step by step. Watch how the running maximum compares to the step number, and notice that alignment happens only when they match.

The answer is 2. The prefix is aligned at step 4 (positions 1 through 4 are all set) and at step 5 (all positions are set). At every other step, the max position exceeds the step number, meaning there is at least one gap in the prefix.

Complexity analysis

Time is O(n). We iterate through the flips array once, doing O(1) work per step (one comparison and one max update).

Space is O(1). We only store two variables: max_pos and count. We do not need to build the actual binary string or use any auxiliary data structure.

Building blocks

1. Running maximum tracking

The pattern of maintaining the largest value seen so far as you iterate through a sequence:

running_max = 0
for value in sequence:
    running_max = max(running_max, value)

This is one of the simplest streaming aggregates. You see it in problems like Jump Game (tracking the farthest reachable index), Best Sightseeing Pair (tracking the best left endpoint), and any problem where the "worst case so far" determines whether a condition holds. The running maximum is a one-variable summary of all values processed, and it lets you make decisions without rescanning.

2. Contiguous range verification via counting

The pattern of checking whether a set of distinct values covers {1, 2, ..., k} by comparing the count to the maximum:

if max_value == count and all_distinct:
    values_form_contiguous_range = True

This appears in problems involving permutation checking, task completion verification, and array rearrangement. The insight is that if you have k distinct positive integers and the largest is k, they must be 1 through k. No other arrangement is possible. This avoids the need for a hash set or sorted check.

3. Enumerate with offset

The pattern of using enumerate(seq, start) to align loop indices with 1-indexed problem descriptions:

for i, val in enumerate(sequence, 1):
    if condition(i, val):
        process(i, val)

Many LeetCode problems use 1-indexed positions or steps. Using enumerate with a start value of 1 eliminates off-by-one errors and keeps the code clean. You avoid the mental overhead of translating between 0-indexed loops and 1-indexed problem statements.

Edge cases

Before submitting, think through these scenarios:

• Already sorted flips [1, 2, 3, 4, 5]: every step is prefix-aligned. The answer equals n.
• Reverse sorted flips [5, 4, 3, 2, 1]: only the last step is prefix-aligned. The answer is 1.
• Single element [1]: one flip, one position. Always prefix-aligned. Answer is 1.
• Max at the end [2, 3, 4, 5, 1]: only the final step aligns the prefix because the max stays above the step number until step 5.
• Large n: the O(n) solution handles the maximum constraint (n up to 50,000) easily.

From understanding to recall

You have seen how tracking a running maximum eliminates the need to scan the entire prefix at each step. The logic is minimal: update the max, compare to the step number, count the matches. Three lines inside the loop.

But under interview pressure, the subtle details matter. Do you use 0-indexed or 1-indexed steps? Do you compare max_pos == i or max_pos == i + 1? Do you initialize max_pos to 0 or 1? These are not conceptual questions. They are recall questions, and getting them wrong costs you time or correctness.

Spaced repetition is how you lock these details in. You practice writing the running max loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "check if values cover a contiguous range" in a problem description, and the code flows out: track the max, compare to the count, done. No hesitation.

Related posts

• Jump Game - Another problem where tracking a running maximum (farthest reachable index) replaces an expensive per-step check
• Gas Station - A greedy problem where a single running aggregate determines the answer without brute-force simulation
• Maximum Subarray - Kadane's algorithm uses a similar streaming approach, maintaining a running value to avoid rescanning

CodeBricks breaks the prefix-aligned binary string problem into its running maximum tracking and contiguous range verification building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a running-max problem shows up in your interview, you do not think about it. You just write it.