LeetCode 2137 - Pour Water Between Buckets to Make Water Levels Equal

This problem asks us to equalize the water levels in a series of buckets while accounting for a spill loss. Each bucket initially contains some quantity of water given in an array buckets, and every time we pour water from one bucket to another, a percentage of that water…

leetcodemediumarraybinary-search

LeetCode Problem 2137

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

This problem asks us to equalize the water levels in a series of buckets while accounting for a spill loss. Each bucket initially contains some quantity of water given in an array buckets, and every time we pour water from one bucket to another, a percentage of that water, loss, is lost. The goal is to determine the maximum possible water level that all buckets can achieve after optimally redistributing water.

The input buckets is a list of integers representing the gallons of water in each bucket. The loss is an integer between 0 and 99 representing the percentage of water lost during each pour operation. The output is a floating-point number representing the maximum equalized water level across all buckets, accurate to within 10^-5.

Constraints indicate that there can be up to 10^5 buckets, each containing up to 10^5 gallons. This scale makes any approach that simulates every individual pour impractical. Edge cases to consider include all buckets already equal, zero loss, maximum loss, and buckets with zero water.

Approaches

Brute Force

The brute-force approach would involve simulating every possible pour between buckets. For each pair of buckets, pour water from the one with more to the one with less, accounting for loss, until all buckets are equalized. This method is conceptually correct but inefficient: it requires potentially O(n^2) operations per iteration and may need many iterations to converge. Given the constraints (n up to 10^5), this is too slow.

Optimal Approach

The optimal solution relies on binary search on the final water level. Instead of simulating pours directly, we test a candidate water level target and check whether it is achievable given the buckets and the loss.

The key insight is that for each bucket:

  • If a bucket has more water than target, it can provide excess = bucket - target gallons.
  • If a bucket has less water than target, it needs deficit = target - bucket gallons to reach the target.
  • Because pouring loses a percentage of water, deficit / (1 - loss/100) is the actual amount we need to extract from other buckets to satisfy this deficit.

If the total excess is greater than or equal to the total effective deficit, the target level is achievable. This allows us to use binary search over the water level range [0, max(buckets)] with a precision of 1e-6.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2 * iterations) O(1) Simulate each pour; too slow for large n
Optimal O(n * log(max_bucket / precision)) O(1) Binary search on water level; linear scan per check

Algorithm Walkthrough

  1. Initialize the search range low = 0 and high = max(buckets).

  2. Set precision = 1e-6 for stopping criteria.

  3. While high - low > precision, perform binary search:

  4. Compute mid = (low + high) / 2 as a candidate target water level.

  5. Initialize excess = 0 and required = 0.

  6. For each bucket:

  • If bucket > mid, add bucket - mid to excess.
  • If bucket < mid, add (mid - bucket) / (1 - loss / 100) to required.
  1. If excess >= required, mid is achievable; set low = mid.
  2. Otherwise, mid is too high; set high = mid.
  3. After convergence, low is the maximum achievable water level.

Why it works

This works because the condition excess >= required guarantees that the total water that can be redistributed, after accounting for loss, is sufficient to meet the target. Binary search efficiently narrows down the largest feasible value with guaranteed convergence due to monotonicity: if a target is achievable, any smaller target is also achievable.

Python Solution

from typing import List

class Solution:
    def equalizeWater(self, buckets: List[int], loss: int) -> float:
        low, high = 0.0, max(buckets)
        precision = 1e-6
        factor = 1 - loss / 100.0

        while high - low > precision:
            mid = (low + high) / 2.0
            excess, required = 0.0, 0.0
            for water in buckets:
                if water > mid:
                    excess += water - mid
                else:
                    required += (mid - water) / factor
            if excess >= required:
                low = mid
            else:
                high = mid

        return low

Explanation

We define the binary search range from 0 to the maximum bucket water. For each candidate mid, we calculate the total excess water that can be poured and the total required water to reach mid across all buckets. We adjust low and high based on whether the candidate target is feasible, stopping when the range is within 1e-6. The function then returns the largest achievable water level.

Go Solution

func equalizeWater(buckets []int, loss int) float64 {
    low, high := 0.0, 0.0
    for _, water := range buckets {
        if float64(water) > high {
            high = float64(water)
        }
    }

    precision := 1e-6
    factor := 1.0 - float64(loss)/100.0

    for high - low > precision {
        mid := (low + high) / 2.0
        excess, required := 0.0, 0.0
        for _, water := range buckets {
            w := float64(water)
            if w > mid {
                excess += w - mid
            } else {
                required += (mid - w) / factor
            }
        }
        if excess >= required {
            low = mid
        } else {
            high = mid
        }
    }

    return low
}

Explanation

The Go implementation mirrors the Python logic, converting integers to floats to handle the arithmetic precisely. The loop continues until the search range is smaller than 1e-6, ensuring the answer meets the required precision.

Worked Examples

Example 1

Input: buckets = [1,2,7], loss = 80

Binary search candidate mid = 2.0:

Bucket Excess/Required
1 required = (2-1)/0.2 = 5
2 required = (2-2)/0.2 = 0
7 excess = 7-2 = 5

Excess >= Required → 5 >= 5, feasible. Output = 2.0

Example 2

Input: buckets = [2,4,6], loss = 50

Candidate mid = 3.5:

Bucket Excess/Required
2 required = (3.5-2)/0.5 = 3
4 excess = 4-3.5 = 0.5
6 excess = 6-3.5 = 2.5

Excess = 0.5+2.5 = 3, Required = 3 → feasible. Output = 3.5

Example 3

Input: buckets = [3,3,3,3], loss = 40

All buckets already equal → maximum level = 3.0

Complexity Analysis

Measure Complexity Explanation
Time O(n * log(max_bucket / precision)) Each binary search iteration scans all buckets; log factor due to precision of 1e-6
Space O(1) Only constant extra variables are used

The algorithm is efficient because binary search reduces the number of water levels to check, and each check only requires a linear pass through the buckets.

Test Cases

# provided examples
assert abs(Solution().equalizeWater([1,2,7], 80) - 2.0) < 1e-5
assert abs(Solution().equalizeWater([2,4,6], 50) - 3.5) < 1e-5
assert abs(Solution().equalizeWater([3,3,3,3], 40) - 3.0) < 1e-5

# edge cases
assert abs(Solution().equalizeWater([0,0,0], 0) - 0.0) < 1e-5  # all zero, no loss
assert abs(Solution().equalizeWater([100000], 99) - 100000.0) < 1e-5  # single bucket
assert abs(Solution().equalizeWater([0,100000], 0) - 50000.0) < 1e-5  # no loss, large spread
assert abs(Solution().equalizeWater([0,100000], 99) - 50.50505) < 1e-5  # high loss
Test Why
`[1,2,7], 80