2380 Time Needed to Rearrange Binary String Solution

The 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.

Return the number of seconds needed to complete this process.

Example 1:

Input: s = "0110101"
Output: 4
Explanation: 
After one second, s becomes "1011010".
After another second, s becomes "1101100".
After the third second, s becomes "1110100".
After the fourth second, s becomes "1111000".
No occurrence of "01" exists any longer, and the process needed 4 seconds to complete,
so we return 4.

Example 2:

Input: s = "11100"
Output: 0
Explanation:
No occurrence of "01" exists in s, and the processes needed 0 seconds to complete,
so we return 0.

Constraints:

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

Follow up:

Can you solve this problem in O(n) time complexity?

Approach overview

Problem Overview: You are given a binary string. Every second, all occurrences of "01" are replaced with "10" simultaneously. The task is to compute how many seconds are required until the string stops changing.

Approach 1: Simulate Step-by-Step Transformations (O(n²) time, O(1) space)

The most direct method mimics the process exactly as described. Scan the string from left to right and swap every "01" pair into "10" during a single pass. After completing one pass, increment the time counter and repeat until no more swaps occur. Each iteration pushes 1s to the right by at most one position, similar to bubble sort behavior.

This approach uses simple string or array manipulation and falls under simulation. In the worst case (for example "000...111" patterns gradually moving), the process may require up to n passes with an O(n) scan each time, resulting in O(n²) time. Space usage stays O(1) since swaps occur in place.

Approach 2: Analytical Total Number of 01 Pairs (O(n) time, O(1) space)

The simulation hides a useful observation: each 1 must move past all preceding 0s. Instead of performing swaps, track how many zeros appear before each 1. When scanning the string, maintain a counter zeros. Every time a 0 appears, increment it. When encountering a 1 with zeros > 0, that 1 must cross those zeros.

The key detail is that movements cannot happen simultaneously for the same character if previous swaps delay it. Maintain a variable time. For each such 1, update time = max(time + 1, zeros). This models both waiting for earlier swaps and the distance the 1 must travel. The entire string is processed in one pass, making the algorithm O(n) time with O(1) extra space.

This method relies on recognizing the implicit ordering constraints created by repeated swaps, a pattern common in string processing problems and occasionally framed with dynamic programming-style state transitions.

Recommended for interviews: Interviewers usually expect the analytical approach. Writing the simulation first shows you understand the process, but the O(n) counting method demonstrates stronger algorithmic insight by eliminating unnecessary passes.

Approach 1: Simulate Step-by-Step Transformations

This approach involves simulating each operation on the string until stabilization. During each iteration, we transform every '01' to '10'. We repeat this process, updating the string at each step, until_no occurrence of '01' exists.

Python

def time_to_rearrange(s):
    count = 0
    changed = True
    s = list(s)
    while changed:
        changed = False
        i = 0
        while i < len(s) - 1:
            if s[i] == '0' and s[i + 1] == '1':
                s[i], s[i + 1] = s[i + 1], s[i]
                i += 1  # Skip the next character
                changed = True
            i += 1
        if changed:
            count += 1
    return count

Java

public class Rearrange { 

    public int timeToRearrange(String s) {
        int count = 0;
        boolean changed = true;
        char[] arr = s.toCharArray();
        while (changed) {
            changed = false;
            for (int i = 0; i < arr.length - 1; i++) {
                if (arr[i] == '0' && arr[i + 1] == '1') {
                    arr[i] = '1';
                    arr[i + 1] = '0';
                    i++; // Skip the next character
                    changed = true;
                }
            }
            if (changed) {
                count++;
            }
        }
        return count;
    }
}

C++

#include <string>
using namespace std;

int timeToRearrange(string s) {
    int count = 0;
    bool changed = true;
    while (changed) {
        changed = false;
        for (size_t i = 0; i < s.size() - 1; i++) {
            if (s[i] == '0' && s[i + 1] == '1') {
                swap(s[i], s[i + 1]);
                i++; // Skip the next character
                changed = true;
            }
        }
        if (changed) {
            count++;
        }
    }
    return count;
}

JavaScript

function timeToRearrange(s) {
    let count = 0;
    let changed = true;
    s = s.split('');
    while (changed) {
        changed = false;
        for (let i = 0; i < s.length - 1; i++) {
            if (s[i] === '0' && s[i + 1] === '1') {
                [s[i], s[i + 1]] = [s[i + 1], s[i]];
                i++; // Skip the next character
                changed = true;
            }
        }
        if (changed) {
            count++;
        }
    }
    return count;
}

#include <string.h>

int timeToRearrange(char* s) {
    int count = 0;
    int len = strlen(s);
    int changed = 1;
    while (changed) {
        changed = 0;
        for (int i = 0; i < len - 1; i++) {
            if (s[i] == '0' && s[i + 1] == '1') {
                s[i] = '1';
                s[i + 1] = '0';
                i++; // Jump over the next character
                changed = 1;
            }
        }
        if (changed) {
            count++;
        }
    }
    return count;
}

public int TimeToRearrange(string s) {
    int count = 0;
    bool changed = true;
    char[] arr = s.ToCharArray();
    while (changed) {
        changed = false;
        for (int i = 0; i < arr.Length - 1; i++) {
            if (arr[i] == '0' && arr[i + 1] == '1') {
                arr[i] = '1';
                arr[i + 1] = '0';
                i++; // Skip the next character
                changed = true;
            }
        }
        if (changed) {
            count++;
        }
    }
    return count;
}

In Python, the string becomes a list of characters to allow in-place modifications. This enables swapping of '01' to '10', continuing until no changes remain viable, tracking transformations each step.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Analytical Total Number of 01 Pairs Approach

This analytical approach leverages the fact that the process will continue until all '01' pairs are absent. Step by step, each '01' pair is replaced, contributing to all zeros moving towards the end of the string. The process depends on the initial arrangement of zeros and ones.

Python

def time_to_rearrange(s):
    ones = 0
    seconds = 0
    for c in s:
        if c == '1':
            ones += 1
        elif ones > 0:
            seconds = max(seconds, ones)
            seconds += 1
    return seconds

Java

public class Rearrange {

    public int timeToRearrange(String s) {
        int ones = 0, seconds = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                ones++;
            } else if (ones > 0) {
                seconds = Math.max(seconds, ones);
                seconds++;
            }
        }
        return seconds;
    }
}

C++

#include <string>
using namespace std;

int timeToRearrange(string s) {
    int ones = 0, seconds = 0;
    for (char c : s) {
        if (c == '1') {
            ones++;
        } else if (ones > 0) {
            seconds = max(seconds, ones);
            seconds++;
        }
    }
    return seconds;
}

JavaScript

function timeToRearrange(s) {
    let ones = 0, seconds = 0;
    for (let c of s) {
        if (c === '1') {
            ones++;
        } else if (ones > 0) {
            seconds = Math.max(seconds, ones);
            seconds++;
        }
    }
    return seconds;
}

#include <string.h>

int timeToRearrange(char* s) {
    int ones = 0, seconds = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '1') {
            ones++;
        } else if (ones > 0) {
            seconds = (seconds > ones) ? seconds : ones;
            seconds++;
        }
    }
    return seconds;
}

public int TimeToRearrange(string s) {
    int ones = 0, seconds = 0;
    foreach (char c in s) {
        if (c == '1') {
            ones++;
        } else if (ones > 0) {
            seconds = Math.Max(seconds, ones);
            seconds++;
        }
    }
    return seconds;
}

Python's solution employs the counting of ones to determine time impact when a '0' is found after them, continuing until no zero or one mismatches remain to swap.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Default Approach

func secondsToRemoveOccurrences(s string) int {
	cs := []byte(s)
	ans := 0
	find := true
	for find {
		find = false
		for i := 0; i < len(cs)-1; i++ {
			if cs[i] == '0' && cs[i+1] == '1' {
				cs[i], cs[i+1] = cs[i+1], cs[i]
				i++
				find = true
			}
		}
		if find {
			ans++
		}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Simulate Step-by-Step Transformations	Time Complexity: O(n^2) Space Complexity: O(1)
Analytical Total Number of 01 Pairs Approach	Time Complexity: O(n) Space Complexity: O(1)
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Simulate Step-by-Step Transformations	O(n²)	O(1)	When implementing the process exactly as described or verifying behavior during interviews
Analytical Total Number of 01 Pairs	O(n)	O(1)	Preferred solution for interviews and large inputs where repeated simulation would be too slow

Frequently asked questions

Is Time Needed to Rearrange a Binary String easy or hard?

The problem is rated Medium because the straightforward simulation is easy to code but inefficient. Recognizing the pattern that each '1' must pass preceding zeros—and translating that into a single-pass formula—requires stronger algorithmic insight.

How to solve Time Needed to Rearrange a Binary String in O(n)?

Traverse the string once while tracking the number of zeros seen so far. When encountering a '1' and there are preceding zeros, compute the time required using time = max(time + 1, zeros). This formula captures both the distance the '1' must travel and delays caused by earlier swaps, producing the answer in linear time.

Time Needed to Rearrange a Binary String Python or Java solution?

Python and Java implementations typically follow the same O(n) logic: iterate through the string, count zeros, and update a time variable using max(time + 1, zeros) whenever a '1' appears after zeros. The algorithm is short and requires only constant extra memory.

What is the best approach for Time Needed to Rearrange a Binary String?

The optimal approach scans the string once while counting how many zeros appear before each '1'. When a '1' appears after zeros, update the required time using time = max(time + 1, zeros). This analytical method avoids repeated simulation and runs in O(n) time with O(1) space.

Is Time Needed to Rearrange a Binary String asked at Google/Amazon/Meta?

Problems involving swap simulations, string transformations, and counting constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often test whether candidates recognize when a simulation can be converted into a linear analytical solution.

What data structure is used in Time Needed to Rearrange a Binary String?

The optimal solution does not require complex data structures. It uses simple counters while iterating through the string. The simulation version may treat the string as a mutable array or character list to swap adjacent elements.

What is the time complexity of Time Needed to Rearrange a Binary String?

The optimal analytical solution runs in O(n) time because it processes each character exactly once while maintaining counters for zeros and total time. A direct simulation approach can take O(n²) time in the worst case because the string may require up to n transformation rounds.

Time Needed to Rearrange a Binary String solution and explanation

The problem

Approach overview

Approach 1: Simulate Step-by-Step Transformations

Approach 2: Analytical Total Number of 01 Pairs Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Time Needed to Rearrange a Binary String solution and explanation

The problem

Approach overview

Approach 1: Simulate Step-by-Step Transformations

Approach 2: Analytical Total Number of 01 Pairs Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems