Skip to main content
Talentd

Water and Jug Problem - Solution & Explanation

MediumMathDepth-First SearchBreadth-First Search22 min readAsked at: Amazon, Microsoft, Apple +5
Practice this problem

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:

  1. Fill the 5-liter jug (0, 5).
  2. Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
  3. Empty the 3-liter jug (0, 2).
  4. Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
  5. Fill the 5-liter jug again (2, 5).
  6. 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).
  7. 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.

Approach 1: Mathematical Approach Using GCD

If you can reach a particular amount "target" of water using the two jug capacities x and y, it should be mathematically possible by considering the greatest common divisor (GCD) of x and y. This is based on the Diophantine equation which shows that target amount can be formed using a linear combination of jug capacities only if it is a multiple of the GCD. The condition to determine if we can measure exactly 'target' liters is if target <= x + y and target is a multiple of GCD(x, y).

The function gcd calculates the greatest common divisor of two numbers. The function canMeasureWater checks whether the target is reachable by ensuring the target is less than or equal to the sum of the jug capacities and is a multiple of the GCD of the jug capacities.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log(min(x, y))) due to the GCD computation.
Space Complexity: O(1) as we only use a constant amount of additional space.

Try this approach in the editor →

Approach 2: Breadth-First Search (BFS) Approach

Breadth-First Search (BFS) can be used to simulate the water jug operations. We treat each state (a, b) of the jugs as a node, where a and b are the current water levels in the two jugs respectively. From each node, we can perform possible operations to reach new states, effectively exploring the state space until the target is found or all options are exhausted.

This C function uses a BFS algorithm with a queue to explore all possible water jug states until the target is found or all states are exhausted. A simple 2D array keeps track of visited states to avoid re-exploration.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(x * y) as each state is visited once.
Space Complexity: O(x * y) for storing visited states.

Try this approach in the editor →

Approach 3: DFS

Let's denote jug1Capacity as x, jug2Capacity as y, and targetCapacity as z.

Next, we design a function dfs(i, j), which represents whether we can get z liters of water when there are i liters of water in jug1 and j liters of water in jug2.

The execution process of the function dfs(i, j) is as follows:

  • If (i, j) has been visited, return false.
  • If i = z or j = z or i + j = z, return true.
  • If we can get z liters of water by filling jug1 or jug2, or emptying jug1 or jug2, return true.
  • If we can get z liters of water by pouring water from jug1 into jug2, or pouring water from jug2 into jug1, return true.

The answer is dfs(0, 0).

The time complexity is O(x + y), and the space complexity is O(x + y). Here, x and y are the sizes of jug1Capacity and jug2Capacity respectively.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Mathematical Approach Using GCD

Time Complexity: O(log(min(x, y))) due to the GCD computation.
Space Complexity: O(1) as we only use a constant amount of additional space.

Breadth-First Search (BFS) Approach

Time Complexity: O(x * y) as each state is visited once.
Space Complexity: O(x * y) for storing visited states.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 ApproachO(log(min(x, y)))O(1)Optimal solution when recognizing the number theory property behind jug operations

Video Solution

[BFS & Math] LeetCode 365. Water and Jug Problem English Version • happygirlzt • 12,078 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Water and Jug Problem easy or hard?
Water and Jug Problem is generally classified as Medium difficulty. The brute-force state search using BFS is straightforward, but recognizing the mathematical GCD shortcut requires familiarity with number theory concepts.
Water and Jug Problem Python/Java solution
Most implementations either compute gcd(x, y) directly for the optimal solution or simulate jug operations using BFS. Both Python and Java versions typically include a gcd helper function or a queue-based traversal for the state graph.
How to solve Water and Jug Problem in O(log n)?
Use the number theory property derived from Bézout’s identity. First check if target <= x + y. Then compute gcd(x, y). If target is divisible by that gcd, the exact amount can be measured. The gcd computation via the Euclidean algorithm runs in O(log n).
What is the best approach for Water and Jug Problem?
The optimal approach uses the mathematical GCD insight. If target is greater than the combined capacity x + y, measuring it is impossible. Otherwise compute gcd(x, y) and check whether target % gcd(x, y) == 0. This solution runs in O(log(min(x, y))) time with O(1) space.
Is Water and Jug Problem asked at Google/Amazon/Meta?
Water and Jug Problem is a classic algorithm question that appears in interview preparation sets and coding platforms like LeetCode. Variants of the problem have been reported in interviews at companies such as Google and Amazon because it tests both graph search and mathematical reasoning.
What data structure is used in Water and Jug Problem?
The BFS approach uses a queue and a visited set to track explored jug states represented as pairs (a, b). Each state corresponds to a node in an implicit graph where edges represent valid operations like fill, empty, or pour.
What is the time complexity of Water and Jug Problem?
The optimal mathematical solution runs in O(log(min(x, y))) time because it relies on the Euclidean algorithm to compute the greatest common divisor. A BFS or DFS state search solution explores jug states and takes O(x * y) time and space.

Ready to solve this problem?

Practice Water and Jug Problem with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer