Number of Times Binary String Is Prefix-Aligned - Video Solutions

Problem Overview: You receive an array flips where flips[i] represents the position turned from 0 to 1 at step i. After each flip, check whether the binary string is prefix-aligned. A string is prefix-aligned when every position from 1 to k is 1 and the remaining positions are still 0. The task is to count how many steps satisfy this condition.

Approach 1: Track Highest Flipped Index (O(n) time, O(1) space)

This approach observes that a prefix becomes fully aligned when the highest flipped position equals the number of flips performed so far. Iterate through flips while maintaining maxIndex, the largest position that has been turned to 1. At step i (0-based), exactly i + 1 bits have been flipped. If maxIndex == i + 1, then all positions from 1 to maxIndex must already be set to 1, meaning the prefix is perfectly aligned. Increment a counter each time this condition holds. The algorithm performs a single pass through the array with constant extra variables, giving O(n) time and O(1) space. This technique is essentially a greedy simulation over the array of flips.

Approach 2: Use a Set to Track Flipped Indices (O(n) time, O(n) space)

Another way to simulate the process is by storing every flipped index inside a hash set. After each flip, insert the index and track the current maximum flipped position. When the number of elements in the set equals the maximum flipped index, the prefix from 1 to maxIndex must be fully turned on. This works because the set ensures each flipped position is unique, and the equality check confirms that no gaps exist in the prefix. The approach relies on constant-time hash lookups provided by a hash set. Time complexity remains O(n) because each insertion and check is O(1), but space grows to O(n) due to storing all flipped indices.

The key insight across both methods is recognizing that prefix alignment depends only on the largest flipped index and the number of flips performed so far. No explicit reconstruction of the binary string is required. This turns what looks like a simulation problem into a simple counting condition.

Recommended for interviews: The highest-flipped-index method is the expected solution. It shows you recognize the invariant maxIndex == flipsCount and avoid unnecessary data structures. Discussing the set-based simulation first can demonstrate reasoning about correctness, but the constant-space approach shows stronger algorithmic insight and efficiency.