Time Needed to Rearrange a Binary String - Practice Coding Problems

Time Needed to Rearrange a Binary String - Problem

You are given a binary string s. In one second, all occurrences of "01" are simultaneously replaced with "10".

This process repeats until no occurrences of "01" exist in the string.

Return the number of seconds needed to complete this process.

Input & Output

Example 1 — Basic Case

$ Input: s = "0110"

› Output: 2

💡 Note: Second 1: "0110" → "1001" (replace 01 with 10). Second 2: "1001" → "1010" → "1100". No more "01" patterns exist, so 2 seconds total.

Example 2 — Single Swap

$ Input: s = "01"

› Output: 1

💡 Note: Second 1: "01" → "10". No more "01" patterns, so 1 second total.

Example 3 — No Swaps Needed

$ Input: s = "1100"

› Output: 0

💡 Note: Already sorted with all 1's before 0's. No "01" patterns exist, so 0 seconds needed.

Constraints

1 ≤ s.length ≤ 1000
s[i] is either '0' or '1'

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Binary string with '01' patterns that need rearranging

Transformation

All '01' become '10' simultaneously each second

Final State

Count total seconds until no '01' patterns remain

Key Takeaway

🎯 Key Insight: Count how many zeros each 1 needs to pass through - the maximum determines the total time

Asked in

G Google 15 f Facebook 12

The key insight is that each '1' will eventually move past all '0's to its right. Instead of simulating, count zeros to the right of each '1' - the maximum count is the answer. Best approach is the Count Zeros method. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Count Zeros Approach	O(n)	O(1)	Count how many zeros each 1 needs to pass through to reach its final position
Simulation Approach	O(n²)	O(n)	Repeatedly replace all "01" patterns with "10" until no more changes occur

Count Zeros Approach — Algorithm Steps

Step 1: Traverse string from right to left, counting zeros encountered
Step 2: For each 1, record how many zeros it needs to pass
Step 3: Return maximum count among all 1's

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Right to Left

Count zeros encountered while moving left

Track Maximum

For each 1, record current zero count

Return Max

Maximum zero count is the answer

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(char* s) {
    int zeros = 0;
    int maxTime = 0;
    int len = strlen(s);
    
    // Traverse from right to left
    for (int i = len - 1; i >= 0; i--) {
        if (s[i] == '0') {
            zeros++;
        } else { // s[i] == '1'
            maxTime = max(maxTime, zeros);
        }
    }
    
    return maxTime;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0; // remove newline
    
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string from right to left

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track counts

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 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

Count Zeros Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler