Skip to main content
Talentd

Time Needed to Rearrange a Binary String - Solution & Explanation

MediumStringDynamic ProgrammingSimulation12 min readAsked at: Amazon, Salesforce, PayPal +2
Practice this problem

Problem Statement

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.

The C code simulates the process of transforming '01' to '10'. It uses a flag changed to detect if any transformation was made in an iteration. The process continues iterating over the string until no transformations occur, accounting each transformation cycle to count.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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.

The C solution calculates the number of '01' pairs based on the number of '1's encountered as zeros are processed. This method accounts the number of swaps possible only when a '0' occurs after some '1's, simulating the sequence indirectly until no conflicts remain.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

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

Video Solution

2380. Time Needed to Rearrange a Binary String (Leetcode Medium) • Programming Live with Larry • 1,814 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Time Needed to Rearrange a Binary String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Swaps to Group All 1's Together

Next

Minimum Swaps to Group All 1's Together II