2137. Pour Water Between Buckets to Make Water Levels Equal

MediumArrayBinary Search
Leetcode Link

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:

  1. If it's possible to make the water level v in all buckets without violating the conditions, then any value lower than v would also be possible because you would just spill less water.
  2. If it's impossible to achieve the water level v, then any value higher than v 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement recursion?

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 level v is achievable. It calculates total excess water (a) that can be moved from buckets with water levels above v and the total required water (b) to be poured into buckets below the level v, 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) where v is the target level, x is the current level, and loss 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 than 1e-5. At this point, the value of l 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:

  1. Initialize the lower (l) and upper (r) bounds for the binary search. l starts at 0, and r starts at the maximum value in buckets.

  2. Perform the binary search: a. Calculate the midpoint (mid) between the current bounds l and r. b. Utilize the check function to see if it's possible to equalize water to the level mid. The function does this by simulating the water pouring and spillage process. c. If the check function returns True, it means it's possible to equalize at least to the level mid. Hence, update the lower bound to mid. d. If the check function returns False, update the upper bound to mid.

  3. Repeat the binary search process until the difference between l and r is less than 1e-5. The lower bound l will then give us the maximum achievable level with the given loss percentage.

  4. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example 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 between l and r. Initially, mid = (0 + 20) / 2 = 10.
  • Use the check function to determine if we can equalize all buckets to level 10 after considering the 5% loss in transfers.

Step 3: Apply the check function:

  • Start with the total excess water a and required water b set to 0.
  • Bucket 1 (buckets[0]): Has 10 gallons, which is equal to mid, no action needed.
  • Bucket 2 (buckets[1]): Has 15 gallons, which is more than mid. We can move (15 - 10) = 5 gallons out. No spillage occurs when removing water, so a += 5.
  • Bucket 3 (buckets[2]): Has 20 gallons, also more than mid. We can move (20 - 10) = 10 gallons out. Again, no spillage when removing water, so a += 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 to mid. Set l to mid which is now 10.

Step 4: Repeat the binary search process with the new bounds:

  • Now l = 10 and r = 20, calculate a new mid = (10 + 20) / 2 = 15.
  • Running the check function with mid = 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 to mid.
    • 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 approximately 5.26 gallons for Bucket 1, so a < b.

Since a isn't sufficient to cover b, we adjust the upper bound:

  • Set r to mid.

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
Not Sure What to Study? Take the 2-min Quiz：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

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) and r (high) is greater than 1e-5. In each iteration, this range is halved. Therefore, the number of iterations needed for the binary search to converge is O(log(Range/1e-5)), where Range 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 a O(n) complexity, where n 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 the check 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Recommended Readings

Binary Search Speedrun

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫