Problem Description

You have n balls arranged in a row on a table. Each ball is either black or white.

You're given a binary string s of length n where:

• '1' represents a black ball
• '0' represents a white ball
• The string is 0-indexed (positions are numbered from 0 to n-1)

In each step, you can swap two adjacent balls.

Your goal is to arrange all the balls so that:

• All white balls ('0') are on the left side
• All black balls ('1') are on the right side

Return the minimum number of steps (swaps) needed to achieve this arrangement.

For example, if s = "101", you would need to swap the middle '0' with the rightmost '1' to get "011", which takes 1 step.

Intuition

The key insight is that we want all '1's (black balls) to end up on the right side. Instead of simulating actual swaps, we can count how many positions each '1' needs to move to reach its final position.

Think about it this way: if we process the string from right to left, we can keep track of how many '1's we've already "placed" on the right. When we encounter a new '1', we know exactly where it should go - it should be placed just before all the '1's we've already seen.

For a '1' at position i, if we've already placed cnt number of '1's on the right, then this '1' should ultimately be at position n - cnt - 1 (where n is the length of string). The number of steps needed to move it there is (n - cnt - 1) - i = n - i - cnt - 1.

However, since we're counting from position i and there are already cnt balls to its right that are '1's, and we increment cnt before calculating, the formula becomes n - i - cnt.

By traversing from right to left and accumulating these distances for each '1', we get the total minimum number of swaps needed. This works because each '1' independently needs to move a certain distance to the right, and these movements don't interfere with each other when counted this way.

Learn more about Greedy and Two Pointers patterns.

Solution Approach

We implement the solution by traversing the string from right to left and counting the moves needed for each '1' to reach its final position.

Here's the step-by-step implementation:

1. Initialize variables:

   • n = len(s): Store the length of the string
   • ans = 0: Accumulator for the total number of moves
   • cnt = 0: Counter for the number of '1's we've seen so far from the right

2. Traverse from right to left:

   for i in range(n - 1, -1, -1):

   We iterate through the string backwards, from index n-1 to 0.

3. Process each '1':

   if s[i] == '1':
       cnt += 1
       ans += n - i - cnt

   When we encounter a '1' at position i:

   • First, increment cnt by 1 (we've found another '1')
   • Calculate the distance this '1' needs to move: n - i - cnt
     • n - cnt would be the target position (counting from 1)
     • i is the current position (counting from 0)
     • So the distance is (n - cnt) - (i + 1) = n - i - cnt
   • Add this distance to our total ans

4. Return the result: After processing all positions, ans contains the minimum number of swaps needed.

The algorithm runs in O(n) time with O(1) extra space, making it highly efficient. Each '1' is processed exactly once, and we calculate its contribution to the total moves in constant time.

Example Walkthrough

Let's trace through the algorithm with s = "10101".

Initial Setup:

• n = 5 (length of string)
• ans = 0 (total moves counter)
• cnt = 0 (count of '1's seen from right)
• Final goal: All '0's on left, all '1's on right → "00111"

Step-by-step traversal (right to left):

i = 4: s[4] = '1'

• This is a '1', so we process it
• cnt = 1 (increment count)
• This '1' needs to move to position: n - cnt = 5 - 1 = 4
• Current position is 4, so moves needed: n - i - cnt = 5 - 4 - 1 = 0
• ans = 0 + 0 = 0

i = 3: s[3] = '0'

• This is a '0', skip it (it will naturally move left)
• cnt = 1, ans = 0

i = 2: s[2] = '1'

• This is a '1', so we process it
• cnt = 2 (increment count)
• This '1' needs to move to position: n - cnt = 5 - 2 = 3
• Current position is 2, so moves needed: n - i - cnt = 5 - 2 - 2 = 1
• ans = 0 + 1 = 1

i = 1: s[1] = '0'

• This is a '0', skip it
• cnt = 2, ans = 1

i = 0: s[0] = '1'

• This is a '1', so we process it
• cnt = 3 (increment count)
• This '1' needs to move to position: n - cnt = 5 - 3 = 2
• Current position is 0, so moves needed: n - i - cnt = 5 - 0 - 3 = 2
• ans = 1 + 2 = 3

Result: ans = 3

Verification: To transform "10101" → "00111":

• Move '1' at index 0 past two '0's (2 swaps): "01101" → "01011"
• Move '1' at index 2 past one '0' (1 swap): "01011" → "00111"
• Total: 3 swaps ✓

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string. The algorithm iterates through the string once from right to left (from index n-1 to 0), performing constant-time operations at each position. Since we visit each character exactly once, the total time complexity is linear with respect to the input size.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. The variables n, ans, cnt, and i are all scalar values that don't grow with the input. No additional data structures like arrays, lists, or recursion stacks are used, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Direction of Traversal

A common mistake is traversing from left to right instead of right to left. When traversing left to right, tracking where each '0' should go becomes more complex because you need to know how many '0's are ahead of the current position.

Wrong approach:

def minimumSteps(self, s: str) -> int:
    n = len(s)
    total_steps = 0
    zeros_count = 0
  
    # Wrong: traversing left to right
    for i in range(n):
        if s[i] == '0':
            zeros_count += 1
            # This calculation becomes complicated
            total_steps += i - (zeros_count - 1)
  
    return total_steps

Solution: Always traverse from right to left when counting moves for '1's to reach their final positions on the right side.

2. Off-by-One Error in Position Calculation

Another frequent error is miscalculating the target position or the distance a '1' needs to move.

Wrong calculation:

# Incorrect: forgetting to account for other '1's already counted
steps_for_this_one = (string_length - 1) - current_index

# Or incorrect: using wrong formula
steps_for_this_one = string_length - current_index - ones_count + 1

Solution: The correct formula is (string_length - ones_count) - current_index. Remember that:

• Target position for the k-th '1' from the right is n - k
• Current position is current_index
• Distance = Target - Current = (n - k) - current_index

3. Counting '0's Instead of '1's

Some may try to count '0's and calculate their movements to the left, which can lead to confusion about indexing and position calculations.

Wrong approach:

def minimumSteps(self, s: str) -> int:
    n = len(s)
    total_steps = 0
    zeros_seen = 0
  
    for i in range(n):
        if s[i] == '0':
            # Trying to calculate how far left this '0' needs to go
            total_steps += i - zeros_seen
            zeros_seen += 1
  
    return total_steps

Solution: Stick to counting '1's from right to left. This approach is more intuitive because:

• We know exactly where each '1' should end up (rightmost positions)
• The calculation is straightforward: each '1' moves to position n - count_of_ones_seen

4. Not Understanding the Problem Correctly

Some might think each ball needs to be moved individually to its final position, not realizing that adjacent swaps can be optimized.

Solution: Understand that when we count the distance each '1' needs to move, we're actually counting the number of '0's it needs to "jump over" to reach its final position. This automatically accounts for the minimum number of swaps needed.