Solution Approach

The solution implements binary search on floating-point numbers to find the maximum achievable water level using the boundary-finding template.

The Feasible Function:

For each candidate water level v, we check if it's achievable by comparing excess water to required water:

def feasible(target_level):
    water_available = 0.0
    water_needed = 0.0
    for current_water in buckets:
        if current_water >= target_level:
            water_available += current_water - target_level
        else:
            water_needed += (target_level - current_water) * 100 / (100 - loss)
    return water_available >= water_needed

• Variable water_available accumulates the total excess water from buckets above level v
• Variable water_needed accumulates the total water that needs to be poured (accounting for loss)
• For buckets below level v, we calculate the actual amount to pour using the formula: (v - x) * 100 / (100 - loss)

Binary Search with Template Pattern:

Since we're searching on floating-point values, we use a precision-based loop instead of integer boundaries. The search creates a pattern where:

• Low values are feasible (we have enough excess water)
• High values are not feasible (not enough water after accounting for loss)

We search for the boundary - the maximum level that's still feasible.

left, right = 0.0, max(buckets)
epsilon = 1e-5

while right - left > epsilon:
    mid = (left + right) / 2
    if feasible(mid):
        left = mid  # mid is achievable, try higher
    else:
        right = mid  # mid is not achievable, try lower

When the loop terminates, left contains the maximum achievable water level (the last feasible value found).

Time Complexity: O(n × log(M / ε)) where n is the number of buckets, M is the maximum bucket value, and ε = 1e-5 is the precision Space Complexity: O(1) as we only use a constant amount of extra space

Example Walkthrough

Let's walk through a small example with buckets = [10, 5, 15] and loss = 20%.

Initial Setup:

• We have 3 buckets with 10, 5, and 15 gallons respectively
• Total water = 30 gallons
• When pouring, we lose 20% of the water

Binary Search Process:

Iteration 1:

• Search range: left = 0, right = 15 (max bucket value)
• mid = 7.5
• Check if we can achieve 7.5 gallons in each bucket:
  • Bucket 0 (10 gal): excess = 10 - 7.5 = 2.5 gallons
  • Bucket 1 (5 gal): needs 7.5 - 5 = 2.5 gallons to arrive
    • Must pour: 2.5 × 100/(100-20) = 2.5 × 1.25 = 3.125 gallons
  • Bucket 2 (15 gal): excess = 15 - 7.5 = 7.5 gallons
  • Total excess available: 2.5 + 7.5 = 10 gallons
  • Total needed to pour: 3.125 gallons
  • Since 10 ≥ 3.125, level 7.5 is feasible → left = 7.5

Iteration 2:

• Search range: left = 7.5, right = 15
• mid = 11.25
• Check if we can achieve 11.25 gallons in each bucket:
  • Bucket 0 (10 gal): needs 11.25 - 10 = 1.25 gallons to arrive
    • Must pour: 1.25 × 1.25 = 1.5625 gallons
  • Bucket 1 (5 gal): needs 11.25 - 5 = 6.25 gallons to arrive
    • Must pour: 6.25 × 1.25 = 7.8125 gallons
  • Bucket 2 (15 gal): excess = 15 - 11.25 = 3.75 gallons
  • Total excess available: 3.75 gallons
  • Total needed to pour: 1.5625 + 7.8125 = 9.375 gallons
  • Since 3.75 < 9.375, level 11.25 is NOT feasible → right = 11.25

Iteration 3:

• Search range: left = 7.5, right = 11.25
• mid = 9.375
• Check if we can achieve 9.375 gallons:
  • Bucket 0: excess = 10 - 9.375 = 0.625 gallons
  • Bucket 1: needs 9.375 - 5 = 4.375 gallons to arrive
    • Must pour: 4.375 × 1.25 = 5.46875 gallons
  • Bucket 2: excess = 15 - 9.375 = 5.625 gallons
  • Total excess: 0.625 + 5.625 = 6.25 gallons
  • Total needed: 5.46875 gallons
  • Since 6.25 ≥ 5.46875, level 9.375 is feasible → left = 9.375

The binary search continues, narrowing the range until right - left ≤ 1e-5. The final answer converges to approximately 9.5 gallons per bucket.

Verification of the final answer (~9.5):

• Bucket 0: has 10 gal, excess = 0.5 gal
• Bucket 1: needs 4.5 gal to reach 9.5
  • Must pour: 4.5 × 1.25 = 5.625 gal (4.5 arrives, 1.125 is lost)
• Bucket 2: has 15 gal, excess = 5.5 gal
• Total excess: 0.5 + 5.5 = 6 gal
• Total needed to pour: 5.625 gal
• Since 6 > 5.625, this level is achievable with a small margin

Time and Space Complexity

The time complexity is O(n × log M), where n is the length of the array buckets and M is the maximum value in the array buckets.

The analysis breaks down as follows:

• The binary search runs while right - left > 1e-5. Since we start with left = 0 and right = max(buckets), the search space is initially M. The binary search continues until the difference is less than 1e-5, which requires O(log(M/1e-5)) iterations, which simplifies to O(log M) iterations.
• In each iteration of the binary search, the feasible(v) function is called, which iterates through all n elements in the buckets array to calculate the water that can be poured out and the water needed to fill up to level v. This takes O(n) time.
• Therefore, the total time complexity is O(n × log M).

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables left, right, mid, firstTrueLevel, excessWater, and requiredWater, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

Pitfall: Using the while left < right with right = mid pattern instead of the standard boundary-finding template. This problem searches for a maximum value, so we need to track the last feasible level found.

Why it's wrong: Without tracking firstTrueLevel, you might return an incorrect boundary value when the precision threshold is reached.

Solution: Use the template pattern with explicit tracking:

firstTrueLevel = 0.0
while right - left > epsilon:
    mid = (left + right) / 2
    if feasible(mid):
        firstTrueLevel = mid
        left = mid
    else:
        right = mid
return firstTrueLevel

2. Incorrect Loss Calculation Formula

Pitfall: A common mistake is incorrectly calculating how much water needs to be poured to achieve a target amount after accounting for loss. Many developers mistakenly use:

water_needed += (target_level - current_water) / (1 - loss)  # WRONG!

Why it's wrong: The loss parameter is given as a percentage (0-100), not as a decimal (0-1). Using (1 - loss) when loss = 20 would give -19 instead of 0.8.

Solution: Use the correct formula that treats loss as a percentage:

water_needed += (target_level - current_water) * 100 / (100 - loss)

3. Division by Zero When Loss = 100%

Pitfall: The formula (100 - loss) in the denominator causes division by zero when loss = 100, leading to a runtime error.

Solution: Add a special case check:

def feasible(target_level: float) -> bool:
    if loss == 100:
        # When loss is 100%, no water can be transferred
        # Only achievable if all buckets already have >= target_level
        return all(water >= target_level for water in buckets)

    # Regular logic for loss < 100
    water_available = 0.0
    water_needed = 0.0
    # ... rest of the function

4. Floating-Point Precision Issues

Pitfall: Using exact equality comparisons or too tight precision thresholds can cause issues:

while right - left > 1e-10:  # Too tight precision might cause infinite loops

Why it's problematic: Floating-point arithmetic has inherent precision limitations. Setting epsilon too small might never satisfy the condition due to rounding errors.

Solution: Use an appropriate epsilon value (typically 1e-5 to 1e-9) and avoid exact comparisons:

epsilon = 1e-5  # Reasonable precision for this problem
while right - left > epsilon:
    # binary search logic

5. Not Handling Edge Cases

Pitfall: Failing to handle special cases like:

• Empty bucket list
• Single bucket (no transfer needed)
• All buckets having the same amount initially

Solution: Add edge case handling:

def equalizeWater(self, buckets: List[int], loss: int) -> float:
    if not buckets:
        return 0.0

    if len(buckets) == 1:
        return float(buckets[0])

    # Check if all buckets are already equal
    if len(set(buckets)) == 1:
        return float(buckets[0])

    # Continue with binary search...