Water and Jug Problem - Video Solutions
[BFS & Math] LeetCode 365. Water and Jug Problem English Version
Water and Jug Problem - Video Solution
Watch 10 video solutions for Water and Jug Problem, a medium level problem involving Math, Depth-First Search, Breadth-First Search. This walkthrough by happygirlzt has 12,078 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:
- Fill either jug completely with water.
- Completely empty either jug.
- Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.
Example 1:
Input: x = 3, y = 5, target = 4
Output: true
Explanation:
Follow these steps to reach a total of 4 liters:
- Fill the 5-liter jug (0, 5).
- Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
- Empty the 3-liter jug (0, 2).
- Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
- Fill the 5-liter jug again (2, 5).
- Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).
- Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).
Reference: The Die Hard example.
Example 2:
Input: x = 2, y = 6, target = 5
Output: false
Example 3:
Input: x = 1, y = 2, target = 3
Output: true
Explanation: Fill both jugs. The total amount of water in both jugs is equal to 3 now.
Constraints:
1 <= x, y, target <= 103
Approach Overview
Problem Overview: You are given two jugs with capacities x and y. Using fill, empty, and pour operations, determine whether it is possible to measure exactly target liters of water. The challenge is recognizing that the state space is small but the mathematical property behind the operations leads to a constant‑space optimal solution.
Approach 1: Breadth-First Search State Exploration (O(x * y) time, O(x * y) space)
Model each state as a pair (a, b) representing the current amount of water in jug1 and jug2. From any state you generate neighbors by applying the allowed operations: fill a jug, empty a jug, or pour from one jug to the other until one becomes empty or full. Run a BFS starting from (0,0) and track visited states to avoid cycles. If any state satisfies a == target, b == target, or a + b == target, the answer is true. BFS guarantees exploration of all reachable states and works well when demonstrating graph traversal using Breadth-First Search or Depth-First Search.
Approach 2: Mathematical Approach Using GCD (O(log(min(x, y))) time, O(1) space)
The jug operations follow a classic number theory result: any measurable volume must be a multiple of the greatest common divisor of the two jug capacities. If target > x + y, it is impossible because the combined capacity is insufficient. Otherwise compute gcd(x, y). If target % gcd(x, y) == 0, the target amount is measurable; otherwise it is not. This works because repeatedly pouring between jugs effectively generates linear combinations of x and y. The insight comes from Bézout’s identity, which is a standard technique in math-based algorithm problems.
Recommended for interviews: Start by describing the state-space search with BFS since it directly models the problem and proves correctness. Then present the mathematical optimization using GCD. Interviewers usually expect the GCD insight because it reduces the problem to O(log n) time and constant space, demonstrating strong problem‑solving and mathematical reasoning.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (State Exploration) | O(x * y) | O(x * y) | When modeling the problem as a graph of states or explaining jug operations step-by-step |
| Mathematical GCD Approach | O(log(min(x, y))) | O(1) | Optimal solution when recognizing the number theory property behind jug operations |