2137. Pour Water Between Buckets to Make Water Levels Equal
Problem Description
You are given an array buckets
where the i
-th bucket contains buckets[i]
gallons of water, and the objective is to equalize the water in all buckets. However, when you pour k
gallons of water from one bucket to another, a certain percentage of the water (loss
percent) is spilled and lost. The challenge is to calculate the maximum amount of water that could be in each bucket after distributing the water as evenly as possible while taking into account the water loss during each pour. The expected output is a floating-point number that represents the maximum water level achievable in each bucket, where the result is considered correct if it's within 10^-5
of the actual answer.
Intuition
To solve this problem, we use a binary search method because we are trying to find a value (the maximum amount of water that can be in each bucket) within a certain range (from 0 to the maximum volume in any of the buckets). The intuition behind using binary search in this context comes from understanding that:
- If it's possible to make the water level
v
in all buckets without violating the conditions, then any value lower thanv
would also be possible because you would just spill less water. - If it's impossible to achieve the water level
v
, then any value higher thanv
would also be impossible as it would require even more water to be transferred and hence, more would be lost due to spilling.
With each midpoint value calculated during the binary search, we simulate the process of equalizing the water to that level and check if it would be possible considering the spilling loss. If it's possible to achieve the water level at the midpoint, it becomes the new lower bound; otherwise, it becomes the new upper bound. We stop the binary search process when the difference between the upper and lower bounds is smaller than 10^-5
, and we return the lower bound as the maximum water level possible in each bucket.
The check
function within the solution plays a critical role - it calculates the total water that can be removed from buckets with excess water (a
) and the total water required to fill buckets with less water than the midpoint value (b
), applying the loss
percentage to each transfer. If a
is greater than or equal to b
, then it's possible to achieve the equalized water level v
.
Learn more about Binary Search patterns.
Solution Approach
The solution provided uses binary search to find the maximum level of water that can be achieved in each bucket. Here's an explanation of the key components of the implementation:
-
Binary Search: Binary search is an efficient algorithm for finding an item from a sorted list of items. In our case, though the list is not explicitly sorted, we know that the maximum level lies between a range – from 0 to the maximum number of gallons in any of the buckets.
-
Check Function: The core of the solution is the
check
function which determines if a certain water levelv
is achievable. It calculates total excess water (a
) that can be moved from buckets with water levels abovev
and the total required water (b
) to be poured into buckets below the levelv
, accounting for the loss during transfer. -
Mathematical Calculations: When transferring water from a bucket with excess water, there's no spillage, hence we subtract directly. But when we need to add water to a bucket with less water, we calculate how much extra water is needed given that there will be a
loss
percent spillage. This is calculated with the formula(v - x) * 100 / (100 - loss)
wherev
is the target level,x
is the current level, andloss
is the percentage lost. -
Convergence Criterion: The solution keeps adjusting the bounds of the binary search until the range between the lower (
l
) and upper (r
) bounds is less than1e-5
. At this point, the value ofl
is close enough to the true answer that it can be returned.
Here's a step-by-step breakdown of how the code implements the solution using the binary search algorithm:
-
Initialize the lower (
l
) and upper (r
) bounds for the binary search.l
starts at 0, andr
starts at the maximum value inbuckets
. -
Perform the binary search: a. Calculate the midpoint (
mid
) between the current boundsl
andr
. b. Utilize thecheck
function to see if it's possible to equalize water to the levelmid
. The function does this by simulating the water pouring and spillage process. c. If thecheck
function returnsTrue
, it means it's possible to equalize at least to the levelmid
. Hence, update the lower bound tomid
. d. If thecheck
function returnsFalse
, update the upper bound tomid
. -
Repeat the binary search process until the difference between
l
andr
is less than1e-5
. The lower boundl
will then give us the maximum achievable level with the given loss percentage. -
Return the lower bound
l
as the final answer.
By repeatedly narrowing the search range, the binary search algorithm efficiently zeroes in on the maximum level of water that can be achieved in each bucket.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Suppose we have the array buckets = [10, 15, 20]
and a loss percentage loss = 5
. We are to calculate the maximum amount of water that could be in each bucket after transferring water while accounting for the spillage.
Step 1: Initialize l
(lower bound) to 0 and r
(upper bound) to the maximum value in buckets
, which is 20.
Step 2: Begin binary search:
- Calculate midpoint
mid
betweenl
andr
. Initially,mid = (0 + 20) / 2 = 10
. - Use the
check
function to determine if we can equalize all buckets to level10
after considering the 5% loss in transfers.
Step 3: Apply the check
function:
- Start with the total excess water
a
and required waterb
set to 0. - Bucket 1 (
buckets[0]
): Has 10 gallons, which is equal tomid
, no action needed. - Bucket 2 (
buckets[1]
): Has 15 gallons, which is more thanmid
. We can move(15 - 10) = 5
gallons out. No spillage occurs when removing water, soa += 5
. - Bucket 3 (
buckets[2]
): Has 20 gallons, also more thanmid
. We can move(20 - 10) = 10
gallons out. Again, no spillage when removing water, soa += 10
. - Total excess
a
is equal to 15 gallons of water.
Next, calculate needed water b
to reach the level mid
for the buckets below mid
, which in this case, there are none. Since no bucket has less than 10 gallons, b = 0
.
Check whether a
can cover b
after accounting for the 5% loss. Here, the a
is more than enough to cover b
, as b
is 0.
Then, update our bounds:
- Since we could equalize to level
10
, let's move the lower bound up tomid
. Setl
tomid
which is now 10.
Step 4: Repeat the binary search process with the new bounds:
- Now
l = 10
andr = 20
, calculate a newmid = (10 + 20) / 2 = 15
. - Running the
check
function withmid = 15
, we find:- From Bucket 1 (
buckets[0]
), we now need(15 - 10) * 100 / (100 - 5)
≈5.26
gallons considering 5% loss. - From Bucket 2 (
buckets[1]
), we have an excess of 0 gallons, since it's now equal tomid
. - From Bucket 3 (
buckets[2]
), we can take away(20 - 15) = 5
gallons with no spillage. - Total excess
a
is 5 gallons, but we need approximately5.26
gallons for Bucket 1, soa < b
.
- From Bucket 1 (
Since a
isn't sufficient to cover b
, we adjust the upper bound:
- Set
r
tomid
.
Step 5: Keep adjusting l
and r
, recalculating mid
, and using the check
function until the difference between l
and r
is less than 1e-5
.
By iterating over this process, the binary search algorithm eventually narrows down to the maximum water level that can be achieved with the spillage taken into account. For this example, let's say the binary search converges to a water level of approx. 12.82 gallons
.
Finally, we return the value that l
has converged to, which in our example would be roughly 12.82 gallons
, as the maximum achievable water level in each bucket.
Solution Implementation
1from typing import List # Import List from typing module for type hinting
2
3class Solution:
4 def equalizeWater(self, buckets: List[int], loss: int) -> float:
5 # Define an internal helper function that checks
6 # if it is possible to equalize the water to volume v
7 def can_equalize_to_volume(v):
8 water_to_remove = 0 # Water to remove from larger buckets
9 water_to_add = 0 # Water to add to smaller buckets
10
11 for water_in_bucket in buckets:
12 if water_in_bucket >= v: # If current bucket has more water than v
13 # Calculate the water to remove without loss
14 water_to_remove += water_in_bucket - v
15 else: # If current bucket has less water than v
16 # Calculate the water to add considering the loss
17 water_to_add += (v - water_in_bucket) * 100 / (100 - loss)
18
19 return water_to_remove >= water_to_add # We can equalize if we have enough water to redistribute
20
21 # Initialize the binary search boundaries
22 left = 0
23 right = max(buckets) # The maximum possible volume is the largest bucket
24
25 # Continue the loop until the precision of 1e-5 is reached
26 while right - left > 1e-5:
27 mid = (left + right) / 2 # Consider the mid volume between left and right
28 # Check if it's possible to equalize water to this mid volume
29 if can_equalize_to_volume(mid):
30 left = mid # If possible, we try to see if there's room for more water
31 else:
32 right = mid # Otherwise, we reduce the target volume
33
34 # Final volume after equalization, rounded to 4 decimal places
35 return round(left, 4)
36
1class Solution {
2 // Function to equalize the water in the buckets considering the loss in pouring.
3 public double equalizeWater(int[] buckets, int loss) {
4 // Start with the lowest possible amount of water, which is 0.
5 double left = 0;
6 // The maximum amount of water can only be as much as the fullest bucket.
7 double right = Arrays.stream(buckets).max().getAsInt();
8
9 // Perform binary search within the precision of 1e-5.
10 while (right - left > 1e-5) {
11 double mid = (left + right) / 2;
12 // If it is possible to equalize to mid liters with the allowed loss, search higher.
13 if (canEqualize(buckets, loss, mid)) {
14 left = mid;
15 }
16 // Otherwise, search lower.
17 else {
18 right = mid;
19 }
20 }
21
22 // Return the maximum possible equal amount of water.
23 return left;
24 }
25
26 // Helper function to check if it is possible to equalize to 'targetVolume' liters.
27 private boolean canEqualize(int[] buckets, int loss, double targetVolume) {
28 double excessWater = 0; // Water to be poured out from fuller buckets.
29 double requiredWater = 0; // Water needed to fill the less full buckets.
30
31 // Iterate through each bucket.
32 for (int waterInBucket : buckets) {
33 // If the bucket has more water than the target, calculate the excess.
34 if (waterInBucket > targetVolume) {
35 excessWater += waterInBucket - targetVolume;
36 }
37 // If the bucket has less water than the target, calculate the required amount.
38 else {
39 requiredWater += (targetVolume - waterInBucket) * 100 / (100 - loss);
40 }
41 }
42
43 // We can equalize the water if we have enough excess to cover the required amount after considering the loss.
44 return excessWater >= requiredWater;
45 }
46}
47
1class Solution {
2public:
3 // Function to find the maximum equal water level that can be achieved
4 // in all buckets after accounting for water loss due to transferring.
5 double equalizeWater(vector<int>& buckets, int loss) {
6 // Initialize the search space for the binary search
7 double left = 0;
8 double right = *max_element(buckets.begin(), buckets.end());
9
10 // Functor to check if a given water level is achievable
11 auto isAchievable = [&](double targetLevel) {
12 double excessWater = 0; // Water to be removed from fuller buckets
13 double requiredWater = 0; // Water needed for emptier buckets, adjusted for loss
14 for (int waterInBucket : buckets) {
15 if (waterInBucket > targetLevel) {
16 // Calculate excess water in buckets higher than target level
17 excessWater += waterInBucket - targetLevel;
18 } else {
19 // Calculate water needed for buckets lower than target level
20 // Adjust for loss percentage
21 requiredWater += (targetLevel - waterInBucket) * 100 / (100 - loss);
22 }
23 }
24 // It's achievable if there is enough excess water to account for losses
25 // when filling the emptier buckets
26 return excessWater >= requiredWater;
27 };
28
29 // Perform binary search to find the precise water level that is achievable
30 while (right - left > 1e-5) { // We use a precision of 1e-5
31 double mid = (left + right) / 2;
32 if (isAchievable(mid)) {
33 // If it's possible to achieve 'mid' level, try for a higher level
34 left = mid;
35 } else {
36 // If 'mid' level is not achievable, try for a lower level
37 right = mid;
38 }
39 }
40
41 // After binary search, left is the highest water level that can be achieved
42 return left;
43 }
44};
45
1function equalizeWater(buckets: number[], loss: number): number {
2 // Define lower and upper bounds for binary search
3 let lowerBound = 0;
4 let upperBound = Math.max(...buckets);
5
6 // Helper function to check if it is possible to equalize at volume 'targetVolume'
7 // with the given loss percentage
8 const canEqualizeToVolume = (targetVolume: number): boolean => {
9 let totalExcessWater = 0;
10 let totalRequiredWater = 0;
11 for (const bucketVolume of buckets) {
12 if (bucketVolume >= targetVolume) {
13 // If the current bucket has more water than targetVolume,
14 // we add the excess water to totalExcessWater
15 totalExcessWater += bucketVolume - targetVolume;
16 } else {
17 // If the current bucket has less water than targetVolume,
18 // we calculate how much water (considering loss) is required to reach
19 // targetVolume and add it to totalRequiredWater
20 totalRequiredWater += (targetVolume - bucketVolume) * 100 / (100 - loss);
21 }
22 }
23 // Return true if there is enough excess water to make up for the required water after loss
24 return totalExcessWater >= totalRequiredWater;
25 };
26
27 // Perform binary search to find the maximum water level possible
28 while (upperBound - lowerBound > 1e-5) {
29 const middleVolume = (lowerBound + upperBound) / 2;
30
31 // Use the helper function to decide which half of the search range to keep
32 if (canEqualizeToVolume(middleVolume)) {
33 lowerBound = middleVolume;
34 } else {
35 upperBound = middleVolume;
36 }
37 }
38
39 // Return the lower bound as the result, which is the maximum water level possible after trimming
40 // the decimal places up to the fifth (which is the precision of our binary search)
41 return lowerBound;
42}
43
Time and Space Complexity
The given Python code performs a binary search on the range of possible water levels to find the correct water level such that the total amount of water after adjusting all buckets equals that level even with water loss during the transfer. Let's break down the time and space complexity:
Time Complexity
The time complexity of this function is determined by the binary search and the loop inside the check
function.
-
Binary Search: The binary search runs while the difference between
l
(low) andr
(high) is greater than1e-5
. In each iteration, this range is halved. Therefore, the number of iterations needed for the binary search to converge isO(log(Range/1e-5))
, whereRange
represents the initial range (max(buckets) - min(buckets)
). -
Check Function: Inside each binary search iteration, a
check
function is called that iterates through all buckets to compare their volume against the mid value. This function has a loop that runs once for each bucket. Therefore, it has aO(n)
complexity, wheren
is the number of buckets.
Multiplying these together, the overall time complexity is O(n * log(Range/1e-5))
. Since 1e-5
is a constant, we can simplify this to O(n * log(Range))
.
Space Complexity
The space complexity is simpler to analyze.
-
There are no additional data structures that grow with the input size. The only extra space used is for a constant number of variables (
a
,b
,l
,r
,mid
, and the space to hold thecheck
function). -
As such, the space complexity is
O(1)
- constant space complexity.
In summary:
- Time Complexity:
O(n * log(Range))
- Space Complexity:
O(1)
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.