Separate Black and White Balls

Separate Black and White Balls is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the In-place Array Modification subpattern.

Problem statement

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.

Example 1:

Input: s = "101" Output: 1 Explanation: We can group all the black balls to the right in the following way: - Swap s[0] and s[1], s = "011". Initially, 1s are not grouped together, requiring at least 1 step to group them to the right.

Example 2:

Input: s = "100" Output: 2 Explanation: We can group all the black balls to the right in the following way: - Swap s[0] and s[1], s = "010". - Swap s[1] and s[2], s = "001". It can be proven that the minimum number of steps needed is 2.

Example 3:

Input: s = "0111" Output: 0 Explanation: All the black balls are already grouped to the right.

Constraints:

- 1 <= n == s.length <= 105

- s[i] is either '0' or '1'.

Topics and companies

Topics: Two Pointers, String, Greedy.

How to practise Separate Black and White Balls on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the length of the string s. We iterate through the string once from right to left. time and O(1), only a few integer variables are used regardless of input size. space.

Open Separate Black and White Balls in the code editor, or read the Separate Black and White Balls editorial for a worked solution with its approach and complexity analysis.

Where Separate Black and White Balls sits in the DSA pattern sheet

• Two Pointers pattern guide
• In-place Array Modification subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Separate Black and White Balls

Other problems that use the same In-place Array Modification and Two Pointers techniques:

• Intersection of Two Arrays — Easy, same subpattern
• Move Pieces to Obtain a String — Medium, same subpattern
• Move Zeroes — Easy, same subpattern
• Remove Duplicates from Sorted Array — Easy, same subpattern
• Remove Duplicates from Sorted Array II — Medium, same subpattern
• Remove Element — Easy, same subpattern