Skip to main content
Talentd

Pour Water Between Buckets to Make Water Levels Equal - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary Search12 min readAsked at: Deutsche Bank
Practice this problem

Problem Statement

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 <= 105
  • 0 <= buckets[i] <= 105
  • 0 <= loss <= 99

Approach Overview

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

Solution

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Precision SearchO(n * k)O(1)Conceptual understanding of surplus/deficit redistribution with transfer loss
Binary Search on Floating-Point AnswerO(n log R)O(1)Optimal solution when the feasibility of a target value is monotonic

Video Solution

2137. Pour Water Between Buckets to Make Water Levels Equal (Leetcode Medium) • Programming Live with Larry • 623 views views

Frequently Asked Questions

Is Pour Water Between Buckets to Make Water Levels Equal easy or hard?
The problem is typically classified as Medium difficulty. The redistribution math is straightforward, but recognizing the monotonic property that enables binary search on a floating-point answer requires solid algorithmic intuition.
Pour Water Between Buckets to Make Water Levels Equal Python/Java solution
Implement binary search over the possible water level. For each candidate level, iterate through the buckets to compute surplus water above the level and deficit below it while applying the transfer loss factor. This logic works the same in Python, Java, C++, Go, and TypeScript.
How to solve Pour Water Between Buckets to Make Water Levels Equal in O(n)?
The problem generally cannot be solved in strict O(n) time because the target water level is not known in advance. Instead, use binary search over the possible answer range. Each step performs an O(n) feasibility check, leading to O(n log R) total complexity.
What is the best approach for Pour Water Between Buckets to Make Water Levels Equal?
Binary search on the answer is the most efficient approach. The algorithm searches for the maximum achievable equal water level and verifies feasibility by computing surplus and deficit across all buckets while accounting for transfer loss. Each feasibility check scans the array once, giving an overall complexity of O(n log R).
Is Pour Water Between Buckets to Make Water Levels Equal asked at Google/Amazon/Meta?
This style of problem appears in interviews at companies like Google, Amazon, and Meta when testing binary search on the answer and numerical reasoning. Variants involving resource redistribution or maximizing feasible thresholds are common in technical interviews.
What data structure is used in Pour Water Between Buckets to Make Water Levels Equal?
The problem primarily uses an array to store bucket water amounts. The algorithm relies on arithmetic calculations and binary search rather than advanced data structures.
What is the time complexity of Pour Water Between Buckets to Make Water Levels Equal?
The optimal binary search approach runs in O(n log R) time, where n is the number of buckets and R is the numeric range of possible water levels. Each binary search step performs a linear scan to compute total surplus and deficit. Space complexity remains O(1).

Ready to solve this problem?

Practice Pour Water Between Buckets to Make Water Levels Equal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Peak Element

Next

Minimum Moves to Equal Array Elements