Number of Times Binary String Is Prefix-Aligned

Number of Times Binary String Is Prefix-Aligned - Problem

Array Medium

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 flips[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.

Input & Output

Example 1 — Basic Case

$ Input: flips = [3,2,4,1,5]

› Output: 1

💡 Note: Step 1: flip bit 3 → [0,0,1,0,0], max=3≠1. Step 2: flip bit 2 → [0,1,1,0,0], max=3≠2. Step 3: flip bit 4 → [0,1,1,1,0], max=4≠3. Step 4: flip bit 1 → [1,1,1,1,0], max=4=4 ✓. Step 5: flip bit 5 → [1,1,1,1,1], max=5≠5. Only 1 prefix-aligned state.

Example 2 — Sequential Order

$ Input: flips = [1,2,3]

› Output: 3

💡 Note: Step 1: flip bit 1 → [1,0,0], max=1=1 ✓. Step 2: flip bit 2 → [1,1,0], max=2=2 ✓. Step 3: flip bit 3 → [1,1,1], max=3=3 ✓. All steps are prefix-aligned.

Example 3 — Reverse Order

$ Input: flips = [4,3,2,1]

› Output: 1

💡 Note: Step 1: flip bit 4 → [0,0,0,1], max=4≠1. Step 2: flip bit 3 → [0,0,1,1], max=4≠2. Step 3: flip bit 2 → [0,1,1,1], max=4≠3. Step 4: flip bit 1 → [1,1,1,1], max=4=4 ✓. Only the last step is prefix-aligned.

Constraints

1 ≤ flips.length ≤ 3 × 10⁴
flips is a permutation of the range [1, n]

Visualization

Tap to expand

Understanding the Visualization

Input

Array of flip positions in order

Process

Track when all positions [1,i] are ones

Output

Count of prefix-aligned states

Key Takeaway

🎯 Key Insight: Prefix-aligned when maximum flipped position equals current step

Asked in

G Google 15 f Facebook 12

Brief HTML summary: The key insight is that a binary string is prefix-aligned after step i if and only if the maximum position flipped so far equals i. Best approach is tracking maximum position in O(n) time with O(1) space, avoiding redundant prefix checking.

Common Approaches

Approach	Time	Space	Notes
✓ Track Maximum Position	O(n)	O(1)	Track the maximum flipped position and compare with current step
Simulate and Check Every Step	O(n²)	O(n)	Simulate flipping bits and check entire prefix after each step

Track Maximum Position — Algorithm Steps

Step 1: Track the maximum position flipped so far
Step 2: After each flip, update the maximum if needed
Step 3: Check if maximum equals current step number
Step 4: Count when condition is met

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Max

Keep maximum flipped position

Compare

Check if max equals current step

Count

Increment when condition is met

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* flips, int n) {
    int count = 0;
    int maxFlipped = 0;
    
    for (int i = 0; i < n; i++) {
        // Update maximum position flipped so far
        maxFlipped = max(maxFlipped, flips[i]);
        
        // If maximum position equals current step (1-indexed), it's prefix-aligned
        if (maxFlipped == i + 1) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array
    int flips[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        flips[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(flips, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the flips array, constant work per flip

✓ Linear Growth

Space Complexity

O(1)

Only need to track the maximum position flipped

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Track Maximum Position — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler