Pseudo-code

text
while string is not sorted:
    found_swap = false
    for i from 0 to n-2:
        if s[i] == '1' and s[i+1] == '0':
            swap(s[i], s[i+1])
            increment swap_count
            found_swap = true
return swap_count

Time Complexity Analysis

The time complexity of this simulation is $O(N^2)$. In the worst-case scenario (e.g., 111...000), every '0' must bubble past every '1'. With $N=10^5$, $N^2$ results in $10^{10}$ operations, which will inevitably cause a Time Limit Exceeded (TLE) error.

Core Insight for Separate Black and White Balls

The key intuition is that we do not need to actually perform the swaps to count them. The number of swaps required to move a specific '0' to its target position is the difference between its current index and the index where it should be.

In the sorted state, all '0's will occupy indices 0, 1, 2, ..., k-1 (where k is the total count of '0's).

We can maintain a pointer, let's call it insert_pos, which represents the next available index on the left for a '0'. As we iterate through the string with a second pointer current, whenever we encounter a '0', we know it belongs at insert_pos.

The cost to move the '0' from current to insert_pos using only adjacent swaps is exactly current - insert_pos. This distance represents the number of '1's currently sitting between the '0' and its destination.

Visual Description: Imagine the array indices as slots. We initialize a pointer insert_pos at index 0. We scan the array with current. When current points to a '0', we visualize a "gap" between current and insert_pos. The size of this gap corresponds to the number of swaps added to our total. After "placing" the '0' (conceptually), we increment insert_pos to point to the next free slot on the left.

Execution Flow

Consider the input s = "11001".

1. Initialization:

   • total_swaps = 0
   • insert_pos = 0

2. Step 1 (current = 0):

   • s[0] is '1'.
   • Ignore. insert_pos remains 0.

3. Step 2 (current = 1):

   • s[1] is '1'.
   • Ignore. insert_pos remains 0.

4. Step 3 (current = 2):

   • s[2] is '0'.
   • Target position is insert_pos (0).
   • Cost: 2 - 0 = 2.
   • total_swaps becomes 2.
   • Increment insert_pos to 1.

5. Step 4 (current = 3):

   • s[3] is '0'.
   • Target position is insert_pos (1).
   • Cost: 3 - 1 = 2.
   • total_swaps becomes 2 + 2 = 4.
   • Increment insert_pos to 2.

6. Step 5 (current = 4):

   • s[4] is '1'.
   • Ignore.

7. Final Result: 4.

   • Explanation: The first '0' jumped over two '1's. The second '0' jumped over two '1's. Total 4 swaps.

Proof of Correctness

The algorithm relies on the invariant that insert_pos always points to the earliest index that is not yet finalized as a '0'. When we encounter a '0' at index current, every index between insert_pos and current must be occupied by '1's (otherwise, those positions would have been filled by previous '0's and insert_pos would have advanced).

Therefore, the distance current - insert_pos is exactly equal to the number of '1's preceding the current '0'. Since we must swap the '0' with every preceding '1' to group them correctly, the sum of these distances yields the minimum total swaps. This is mathematically equivalent to counting inversions where i < j but s[i] == '1' and s[j] == '0'.

Reference Implementation

C++ Solution for LeetCode 2938

cpp
class Solution {
public:
    long long minimumSteps(string s) {
        long long total_swaps = 0;
        int insert_pos = 0; // The slow pointer
        
        // Iterate with current as the fast pointer
        for (int current = 0; current < s.length(); ++current) {
            if (s[current] == '0') {
                // The cost to move this '0' to the insert_pos
                total_swaps += (current - insert_pos);
                
                // Advance the insert position for the next '0'
                insert_pos++;
            }
        }
        
        return total_swaps;
    }
};

Java Solution for LeetCode 2938

java
class Solution {
    public long minimumSteps(String s) {
        long totalSwaps = 0;
        int insertPos = 0; // The slow pointer
        
        // Iterate with current as the fast pointer
        for (int current = 0; current < s.length(); current++) {
            if (s.charAt(current) == '0') {
                // The cost to move this '0' to the insertPos
                totalSwaps += (current - insertPos);
                
                // Advance the insert position for the next '0'
                insertPos++;
            }
        }
        
        return totalSwaps;
    }
}

Python Solution for LeetCode 2938

python
class Solution:
    def minimumSteps(self, s: str) -> int:
        total_swaps = 0
        insert_pos = 0 # The slow pointer
        
        # Iterate with current as the fast pointer
        for current, char in enumerate(s):
            if char == '0':
                # The cost to move this '0' to the insert_pos
                total_swaps += (current - insert_pos)
                
                # Advance the insert position for the next '0'
                insert_pos += 1
                
        return total_swaps