We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Separate Black and White Balls

Number: 3195

Difficulty: Medium

Paid? No

Companies: Microsoft, Google, Amazon, Accenture, 1Kosmos

Problem Description

Given a binary string s representing a sequence of balls where '1' represents a black ball and '0' represents a white ball, determine the minimum number of adjacent swaps required to group all the white balls to the left and all the black balls to the right.

Key Insights

  • Ultimately, we want all white balls to be positioned to the left side and all black balls to the right.
  • A useful insight is that for each black ball, the number of swaps needed is equal to the number of white balls that come after it in the original arrangement.
  • We can compute this efficiently by first counting the total number of white balls and then iterating through the string from left to right.
  • When a black ball is encountered, the current count of white balls (yet to be “passed”) is added to the answer.
  • After processing a white ball, the white ball counter is decremented, as that white ball won’t need to be swapped with any black balls that come later.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as only a few auxiliary variables are used.

Solution

The approach begins by calculating the total number of white balls in the string. Then, by iterating over the string from left to right:

  1. If the current ball is black, add the current count of white balls (which represents how many white balls lie to its right) to a running total of swaps.
  2. If the current ball is white, decrement the count of white balls. This method effectively counts the required swaps in one pass without explicitly performing them, ensuring an optimal solution.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def minSwaps(self, s: str) -> int:
        # Count total white balls ('0') in the string
        white_count = s.count('0')
        swaps = 0
        # Iterate through each ball in the string
        for ball in s:
            # If the ball is black ('1')
            if ball == '1':
                # Add the current number of white balls to the swap count
                swaps += white_count
            else:
                # If the ball is white ('0'), decrement the white_count
                white_count -= 1
        return swaps

# Example usage:
# sol = Solution()
# print(sol.minSwaps("101"))
← Back to All Questions