Water and Jug Problem - Video Solutions

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.