Leetcode Daily Question 15/10/2024 - 2938. Separate Black and White Balls

Problem Description:

There are n balls on a table, each ball has a color black or white. | ------------------------------------------------ | You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively. | ------------------------------------------------ | In each step, you can choose two adjacent balls and swap them. | ------------------------------------------------ | Return the minimum number of steps to group all the black balls to the right and all the white balls to the left.

class Solution:
  def minimumSteps(self, s: str) -> int:
    total = 0
    zero_count = 0
    for i in range(len(s) - 1, -1, -1):
      if s[i] == "0":
        zero_count += 1
      else:
        total += zero_count
    return total

Explanation:

We can solve this by using a greedy approach. Note that every time we have zeros sandwiched between ones, it takes that many steps to swap the 1 to the right since we are only allowed to swap adjacent elements.

So we can iterate from right to left keeping count of zeros. Every time we meet a one we add that many steps to our step counter.

Perhaps it would be easier to understand with a few examples.

Consider "11000111":
To shift 1 at index 1 to the right, we need to do 3 swaps -> "10001111"
To shift 1 at index 0 to the right, we need to do 3 swaps again -> "00011111".

Or "10101010":
To shift 1 at index 6 to the right, we do one swap -> "10101001"
To shift 1 at index 4 to the right, we need 2 swaps -> "10100011"
To shift 1 at index 2 to the right, we need 3 swaps -> "10000111"
To shift 1 at index 0 to the right, we need 4 swpas -> "00001111"

def mininumSteps(s):
  total = 0
  zero_count = 0
  for i in range(len(s) - 1, -1, -1):
    if s[i] == "0":
      zero_count += 1
    else:
      total += zero_count
  return total

The time complexity is O(n) as we traverse the string in reverse exactly once.

The space complexity is O(1) as we only store constant variables.

The full solution can be found near the top of the page.