LeetCode 1375 - Number of Times Binary String Is Prefix-Aligned

The problem asks us to determine how many times a binary string becomes prefix-aligned during a series of bit flips. We

leetcodemediumarray

LeetCode Problem 1375

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

The problem asks us to determine how many times a binary string becomes prefix-aligned during a series of bit flips. We start with a binary string of length n where all bits are 0. We are given a list flips of length n, which represents the order in which bits are flipped from 0 to 1. A binary string is prefix-aligned at step i if the first i bits are all 1 and all remaining bits are 0.

The input flips is 1-indexed, meaning flips[i] refers to the bit position starting at 1. The array is a permutation of [1, n], so each index will be flipped exactly once. The expected output is an integer representing the number of steps where the string is prefix-aligned.

The constraints 1 <= n <= 5 * 10^4 imply that an O(n²) solution would be too slow. Since flips is guaranteed to be a permutation, we do not have to handle duplicates or invalid indices, simplifying the logic. Key edge cases include small arrays, arrays where prefix alignment only occurs at the very end, and arrays where alignment occurs multiple times intermittently.

Approaches

The brute-force approach would simulate the binary string. After each flip, we check whether the first i bits are all 1 and all others are 0. This involves iterating over the string at each step, which leads to O(n²) time complexity. This is correct but inefficient for large n.

The optimal approach relies on a key observation: a prefix-aligned state occurs if, at step i, the maximum index flipped so far equals i. This works because for the first i bits to be all ones, we must have flipped all indices from 1 to i exactly once, and any index larger than i cannot have been flipped yet. By keeping track of the maximum flipped index and comparing it with the current step number, we can determine alignment in O(n) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Simulate the string and check prefix alignment at each step
Optimal O(n) O(1) Track the maximum flipped index; compare with step count

Algorithm Walkthrough

  1. Initialize two variables: max_flipped = 0 to keep track of the maximum index flipped so far and prefix_count = 0 to count prefix-aligned states.
  2. Iterate over the array flips with a loop index i from 1 to n.
  3. For each flips[i], update max_flipped to be the maximum of max_flipped and flips[i].
  4. After updating max_flipped, check if max_flipped == i. If so, increment prefix_count.
  5. Continue the loop until all flips are processed.
  6. Return prefix_count as the number of times the binary string was prefix-aligned.

Why it works: At step i, if the maximum index flipped so far equals i, this guarantees that all indices 1 through i have been flipped exactly once (because there are no gaps in a permutation), which is precisely the condition for the string to be prefix-aligned.

Python Solution

from typing import List

class Solution:
    def numTimesAllBlue(self, flips: List[int]) -> int:
        max_flipped = 0
        prefix_count = 0
        
        for i, flip in enumerate(flips, start=1):
            max_flipped = max(max_flipped, flip)
            if max_flipped == i:
                prefix_count += 1
        
        return prefix_count

In this Python implementation, we loop over flips while keeping track of the maximum flipped index with max_flipped. The loop index i is 1-indexed to match the problem description. Each time max_flipped equals i, we increment the prefix_count. Finally, the function returns the total count.

Go Solution

func numTimesAllBlue(flips []int) int {
    maxFlipped := 0
    prefixCount := 0
    
    for i, flip := range flips {
        step := i + 1
        if flip > maxFlipped {
            maxFlipped = flip
        }
        if maxFlipped == step {
            prefixCount++
        }
    }
    
    return prefixCount
}

In Go, we use a standard for loop over the flips slice. Since Go slices are 0-indexed, we calculate step := i + 1 to align with the 1-indexed logic. The maxFlipped variable tracks the maximum index flipped so far, and prefixCount counts prefix-aligned steps.

Worked Examples

Example 1: flips = [3,2,4,1,5]

Step Flip Max Flipped Prefix-Aligned? Count
1 3 3 No 0
2 2 3 No 0
3 4 4 No 0
4 1 4 Yes 1
5 5 5 Yes 2

Example 2: flips = [4,1,2,3]

Step Flip Max Flipped Prefix-Aligned? Count
1 4 4 No 0
2 1 4 No 0
3 2 4 No 0
4 3 4 Yes 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate over flips once, performing constant-time operations per step
Space O(1) Only two integer variables are maintained; no extra data structures are required

The optimal solution is linear in time and constant in space, suitable for the maximum constraint n = 5 * 10^4.

Test Cases

# Provided examples
assert Solution().numTimesAllBlue([3,2,4,1,5]) == 2  # multiple prefix alignments
assert Solution().numTimesAllBlue([4,1,2,3]) == 1     # prefix aligned only at last step

# Edge cases
assert Solution().numTimesAllBlue([1]) == 1          # single element, immediately aligned
assert Solution().numTimesAllBlue([2,1]) == 1        # alignment after flipping smaller index
assert Solution().numTimesAllBlue([1,2,3,4,5]) == 5 # every step aligned
assert Solution().numTimesAllBlue([5,4,3,2,1]) == 1 # alignment only at last step
Test Why
[3,2,4,1,5] Validates multiple intermittent alignments
[4,1,2,3] Validates alignment only at the end
[1] Tests minimum size input
[2,1] Checks early flip of higher index
[1,2,3,4,5] All steps prefix-aligned
[5,4,3,2,1] Only last step prefix-aligned

Edge Cases

The first edge case is when n = 1. Here, the single flip always results in a prefix-aligned string. The implementation handles this naturally since max_flipped will equal i in the first iteration.

The second edge case occurs when the first flip is the largest index. The maximum flipped index may exceed the current step number, so no prefix alignment occurs until enough smaller indices have been flipped. Our algorithm accounts for this by only checking max_flipped == i.

The third edge case is when flips are in increasing order. Every step produces a prefix-aligned string. The algorithm correctly counts each step because max_flipped always equals i. This demonstrates that the solution generalizes to both sparse and sequential permutations.