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.
We notice that if a water volume x meets the condition, then all water volumes less than x also meet the condition. Therefore, we can use binary search to find the maximum water volume that satisfies the condition.
We define the left boundary of the binary search as l=0 and the right boundary as r=max(buckets). During each binary search iteration, we take the midpoint mid of l and r, and check if mid meets the condition. If it does, we update l to mid; otherwise, we update r to mid. After the binary search concludes, the maximum water volume that satisfies the condition is l.
The key to the problem is to determine if a water volume v meets the condition. We can iterate through all buckets, and for each bucket, if its water volume is greater than v, then we need to pour out x-v water volume; if its water volume is less than v, then we need to pour in (v-x)times\frac{100}{100-loss} water volume. If the total volume poured out is greater than or equal to the volume poured in, then v meets the condition.
The time complexity is O(n times log M), where n and M are the length and the maximum value of the array buckets, respectively. The time complexity of binary search is O(log M), and each binary search iteration requires traversing the array buckets, with a time complexity of O(n). The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| 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 |
2137. Pour Water Between Buckets to Make Water Levels Equal (Leetcode Medium) • Programming Live with Larry • 586 views views
Practice Pour Water Between Buckets to Make Water Levels Equal with our built-in code editor and test cases.
Practice on FleetCode