mah-shamim
commented
8 hours ago To solve this problem efficiently, we can use a greedy approach with a two-pointer-like strategy. The key insight is that every 1 (black ball) should be moved past the 0s (white balls) that are to its right, minimizing the total number of swaps.
Approach
-
Track the Number of
0s Encountered:- Iterate through the string from right to left.
- Count the number of
0s encountered so far as you iterate. - When you encounter a
1, each0that is to its right contributes to a swap needed to move this1past those0s. - Add the count of
0s to the total swaps each time you encounter a1.
-
Calculate the Total Swaps:
- The total number of swaps required will be the sum of the number of
0s encountered when processing each1.
- The total number of swaps required will be the sum of the number of
Let's implement this solution in PHP: 2938. Separate Black and White Balls
<?php
/**
* @param String $s
* @return Integer
*/
function minSwapsToGroupBlackBalls($s) {
$n = strlen($s);
$zeroCount = 0; // Tracks the number of '0's encountered
$swaps = 0; // Tracks the minimum number of swaps needed
// Iterate through the string from right to left
for ($i = $n - 1; $i >= 0; $i--) {
if ($s[$i] == '0') {
// Increment the count of zeros when encountering '0'
$zeroCount++;
} elseif ($s[$i] == '1') {
// When encountering '1', add the count of '0's to swaps
$swaps += $zeroCount;
}
}
return $swaps;
}
// Example usage
$s1 = "101";
echo "Input: $s1\n";
echo "Minimum swaps needed: " . minSwapsToGroupBlackBalls($s1) . "\n"; // Output: 1
$s2 = "100";
echo "Input: $s2\n";
echo "Minimum swaps needed: " . minSwapsToGroupBlackBalls($s2) . "\n"; // Output: 2
$s3 = "0111";
echo "Input: $s3\n";
echo "Minimum swaps needed: " . minSwapsToGroupBlackBalls($s3) . "\n"; // Output: 0
?>Explanation:
-
Initialize Counters:
zeroCountis initialized to0and tracks the number of0s encountered while iterating from right to left.swapskeeps track of the minimum swaps needed to group the1s (black balls) together.
-
Iterate Through the String:
- Loop through the string from right to left using a for-loop.
- If the current character is
0, incrementzeroCountas it represents a white ball that will need to be swapped with a1to its left. - If the current character is
1, addzeroCounttoswapsbecause each0encountered after this1contributes to a swap.
-
Return the Total Swaps:
- The accumulated value of
swapsrepresents the minimum number of swaps required to arrange all1s to the right.
- The accumulated value of
Time Complexity
- Time Complexity:
O(n)wherenis the length of the strings. We iterate through the string once and perform constant-time operations for each character. - Space Complexity:
O(1)as we only use a few variables (zeroCountandswaps).
Example Analysis
-
Example 1: Input:
"101"- Iteration from right to left:
s[2] = '1': zeroCount = 0, swaps = 0s[1] = '0': zeroCount = 1, swaps = 0s[0] = '1': zeroCount = 1, add1to swaps, swaps = 1
- Output:
1.
- Iteration from right to left:
-
Example 2: Input:
"100"- Iteration from right to left:
s[2] = '0': zeroCount = 1, swaps = 0s[1] = '0': zeroCount = 2, swaps = 0s[0] = '1': zeroCount = 2, add2to swaps, swaps = 2
- Output:
2.
- Iteration from right to left:
-
Example 3: Input:
"0111"- Iteration from right to left:
s[3] = '1': zeroCount = 0, swaps = 0s[2] = '1': zeroCount = 0, swaps = 0s[1] = '1': zeroCount = 0, swaps = 0s[0] = '0': zeroCount = 1, swaps = 0
- Output:
0(All1s are already grouped).
- Iteration from right to left:
This solution provides an efficient way to determine the minimum steps to separate black and white balls using PHP.
Discussed in https://github.com/mah-shamim/leet-code-in-php/discussions/703
1 <= n == s.length <= 105- `s[i]` is either `'0'` or `'1'`. **Hint:** 1. Every `1` in the string `s` should be swapped with every `0` on its right side. 2. Iterate right to left and count the number of `0` that have already occurred, whenever you iterate on `1` add that counter to the answer.