Watch the video solution for Pour Water Between Buckets to Make Water Levels Equal, a medium level problem involving Array, Binary Search. This walkthrough by Programming Live with Larry has 586 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have n buckets each containing some gallons of water in it, represented by a 0-indexed integer array buckets, where the ith bucket contains buckets[i] gallons of water. You are also given an integer loss.
You want to make the amount of water in each bucket equal. You can pour any amount of water from one bucket to another bucket (not necessarily an integer). However, every time you pour k gallons of water, you spill loss percent of k.
Return the maximum amount of water in each bucket after making the amount of water equal. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: buckets = [1,2,7], loss = 80 Output: 2.00000 Explanation: Pour 5 gallons of water from buckets[2] to buckets[0]. 5 * 80% = 4 gallons are spilled and buckets[0] only receives 5 - 4 = 1 gallon of water. All buckets have 2 gallons of water in them so return 2.
Example 2:
Input: buckets = [2,4,6], loss = 50 Output: 3.50000 Explanation: Pour 0.5 gallons of water from buckets[1] to buckets[0]. 0.5 * 50% = 0.25 gallons are spilled and buckets[0] only receives 0.5 - 0.25 = 0.25 gallons of water. Now, buckets = [2.25, 3.5, 6]. Pour 2.5 gallons of water from buckets[2] to buckets[0]. 2.5 * 50% = 1.25 gallons are spilled and buckets[0] only receives 2.5 - 1.25 = 1.25 gallons of water. All buckets have 3.5 gallons of water in them so return 3.5.
Example 3:
Input: buckets = [3,3,3,3], loss = 40 Output: 3.00000 Explanation: All buckets already have the same amount of water in them.
Constraints:
1 <= buckets.length <= 1050 <= buckets[i] <= 1050 <= loss <= 99Problem Overview: You are given an array where each element represents the amount of water in a bucket. Water can be transferred between buckets, but a fixed percentage is lost during each transfer. The task is to compute the maximum equal water level that all buckets can reach after redistribution.
Approach 1: Brute Force Simulation (High Precision Search) (Time: O(n * k), Space: O(1))
One way to reason about the problem is to test possible target water levels and check whether the redistribution is feasible. For a candidate level x, iterate through the array and track two values: total surplus from buckets above x and total deficit from buckets below x. When water moves from a surplus bucket, a percentage is lost, so only surplus * (1 - loss) contributes to filling deficits. If the adjusted surplus covers the deficit, the level is achievable. Trying many candidate values with a fixed precision eventually approximates the answer, but choosing candidates naively makes this inefficient.
Approach 2: Binary Search on Floating-Point Answer (Time: O(n log R), Space: O(1))
The key observation: if a target level x is achievable, any level smaller than x is also achievable. This monotonic property allows binary search over the answer space. Set the search range between 0 and max(buckets). For each midpoint mid, iterate through the buckets and compute total surplus and deficit. Surplus water is reduced by the transfer loss factor before contributing to the deficit. If the adjusted surplus still covers the deficit, move the search to higher values; otherwise search lower. Continue until the interval becomes very small (e.g., 1e-6 precision). This approach efficiently finds the maximum achievable equal level while scanning the array each iteration.
Recommended for interviews: The expected solution is binary search on the answer combined with a feasibility check. Interviewers look for recognition of the monotonic property and careful handling of floating‑point precision. Explaining the surplus/deficit calculation first shows you understand the redistribution mechanics, while implementing the binary search demonstrates strong problem‑solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Precision Search | O(n * k) | O(1) | Conceptual understanding of surplus/deficit redistribution with transfer loss |
| Binary Search on Floating-Point Answer | O(n log R) | O(1) | Optimal solution when the feasibility of a target value is monotonic |