Scale Engineer

Number of Times Binary String Is Prefix-Aligned

Med
#1275Time: O(n^2) - The outer loop runs `n` times, and for each iteration, the inner loop runs up to `n` times, leading to a quadratic time complexity.Space: O(n) - We use a boolean array of size `n+1` to store the state of the binary string.
Data structures
Array

Prompt

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.

 

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.length
  • 1 <= n <= 5 * 104
  • flips is a permutation of the integers in the range [1, n].

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We maintain a representation of the binary string, flip the bits as instructed, and after each flip, we check the entire prefix of the current length to see if it's composed of all ones.

Algorithm

  • Initialize a boolean array bits of size n + 1 to all false to represent the binary string.
  • Initialize a counter count to 0.
  • Iterate through the flips array from i = 0 to n - 1.
    • Let step = i + 1 be the current step number.
    • Get the position to flip: pos = flips[i].
    • Set bits[pos] to true.
    • Check if the prefix [1, step] is aligned:
      • Assume it is aligned by setting a flag isAligned = true.
      • Start a nested loop from j = 1 to step.
      • If bits[j] is false, it means the prefix is not all ones. Set isAligned = false and break the inner loop.
    • If isAligned remains true after the inner loop, increment count.
  • Return count.

Walkthrough

In this method, we use a boolean array, say bits, of size n + 1 (to handle 1-based indexing easily) to represent the binary string. This array is initialized to all false, corresponding to the initial string of all zeros. We then iterate through the flips array. For each step i (from 0 to n-1), we perform the (i+1)-th flip by setting bits[flips[i]] to true. After each flip, we must check if the string has become prefix-aligned. A string is prefix-aligned after k = i + 1 steps if all bits from 1 to k are true. To verify this, we use a nested loop that iterates from j = 1 to k, checking if bits[j] is true. If we find any bit in this range that is false, the condition is not met. If the entire prefix [1, k] consists of true values, we increment a counter. Finally, this counter gives the total number of times the string was prefix-aligned.

class Solution {    public int numTimesAllBlue(int[] flips) {        int n = flips.length;        boolean[] bits = new boolean[n + 1];        int count = 0;        for (int i = 0; i < n; i++) {            int step = i + 1;            int pos = flips[i];            bits[pos] = true;             boolean isAligned = true;            for (int j = 1; j <= step; j++) {                if (!bits[j]) {                    isAligned = false;                    break;                }            }             if (isAligned) {                count++;            }        }        return count;    }}

Complexity

Time

O(n^2) - The outer loop runs `n` times, and for each iteration, the inner loop runs up to `n` times, leading to a quadratic time complexity.

Space

O(n) - We use a boolean array of size `n+1` to store the state of the binary string.

Trade-offs

Pros

  • Straightforward to implement as it directly models the problem statement.

  • Easy to understand and reason about.

Cons

  • Inefficient due to its O(n^2) time complexity.

  • Likely to result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger input sizes.

Solutions

class Solution {public  int numTimesAllBlue(int[] flips) {    int ans = 0, mx = 0;    for (int i = 1; i <= flips.length; ++i) {      mx = Math.max(mx, flips[i - 1]);      if (mx == i) {        ++ans;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem