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 is prefix-aligned during the flipping process.
Example 1:
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:
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.length1 <= n <= 5 * 104flips is a permutation of the integers in the range [1, n].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.
In this approach, we keep track of the highest index that has been flipped to '1'. At each step, if the highest flipped index equals the current step number (i.e., all indices up to and including the current step are '1'), we increment a counter for the number of times the string is prefix-aligned.
This C solution iterates over the flip indices, updating the maxFlippedIndex with the highest index seen so far. If the maxFlippedIndex equals the current (1-indexed) step number, it means the string is prefix-aligned at this step, so we increment the count.
Time Complexity: O(n), Space Complexity: O(1)
This approach involves using a set to store the indices that have been flipped to '1'. We keep checking from the beginning if all indices up to the current step have been flipped, indicating a prefix alignment.
This Python solution utilizes a set to track flipped indices. After each flip, it checks if all numbers from 1 to current step (i + 1) are included in the set. If true, it increases the count, signifying a prefix alignment.
Python
JavaScript
Time Complexity: O(n^2), Space Complexity: O(n)
We can traverse the array flips, keeping track of the maximum value mx of the elements we have traversed so far. If mx equals the current index i we are traversing, it means that the first i elements have all been flipped, i.e., the prefix is consistent, and we increment the answer.
After the traversal is finished, we return the answer.
The time complexity is O(n), where n is the length of the array flips. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Track Highest Flipped Index | Time Complexity: O(n), Space Complexity: O(1) |
| Use a Set to Track Flipped Indices | Time Complexity: O(n^2), Space Complexity: O(n) |
| Direct Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Track Highest Flipped Index | O(n) | O(1) | Best general solution. Minimal memory and single pass. |
| Hash Set of Flipped Indices | O(n) | O(n) | Useful when explicitly tracking flipped positions during simulation. |
Leetcode: Number of Times Binary String Is Prefix-Aligned (Light Bulb problem) • Dongping Guo • 244 views views
Watch 2 more video solutions →Practice Number of Times Binary String Is Prefix-Aligned with our built-in code editor and test cases.
Practice on FleetCode