How do you solve Water Bottles on LeetCode?

Water Bottles (LeetCode #1518) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The number of full bottles you can drink is directly related to how many empty bottles you can exchange.

What is the brute force solution for Water Bottles?

The brute force approach for Water Bottles is Brute Force, with O(n) time complexity and O(1) space complexity. In the brute force approach, we simulate the entire process of drinking and exchanging bottles. We keep track of how many bottles we can drink until we can no longer exchange empty bottles for full ones. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Water Bottles?

Water Bottles uses the following concepts: Math, Simulation. The recommended patterns to study are: Greedy Algorithms, Simulation.

What are the interview tips for Water Bottles?

Always clarify the problem constraints and edge cases before jumping into coding. Think about both brute force and optimal solutions; interviewers appreciate seeing your thought process. Dry-run your solution with a sample input to catch any logical errors before finalizing your code.

What are common mistakes when solving Water Bottles?

Not accounting for the remaining empty bottles after exchanges. Assuming you can always drink more without checking the exchange condition.

#1518

Water Bottles

Easy

MathSimulationGreedy AlgorithmsSimulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages a mathematical approach to avoid unnecessary iterations. We can directly calculate the total number of bottles drunk by considering the number of exchanges possible in a more efficient way.

⚙️

Algorithm

5 steps

1Step 1: Initialize totalDrunk with numBottles.
2Step 2: While numBottles is greater than or equal to numExchange, do the following:
3Step 3: Calculate how many new full bottles we can get (newBottles = numBottles // numExchange).
4Step 4: Update totalDrunk by adding newBottles, and update numBottles to reflect the new full bottles plus the remaining empty bottles.
5Step 5: Return totalDrunk after exiting the loop.

solution.py7 lines

1def numWaterBottles(numBottles, numExchange):
2    totalDrunk = numBottles
3    while numBottles >= numExchange:
4        newBottles = numBottles // numExchange
5        totalDrunk += newBottles
6        numBottles = newBottles + (numBottles % numExchange)
7    return totalDrunk

ℹ

Complexity note: The complexity remains O(n) as we still iterate based on the number of exchanges, but we avoid unnecessary calculations by directly updating the counts.

1The number of full bottles you can drink is directly related to how many empty bottles you can exchange.
2Each exchange allows you to drink more water, so maximizing exchanges is key.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.