Mastering LeetCode's Water and Jug Problem: Mathematical, BFS, and DFS Solutions

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

The Water and Jug problem (LeetCode 365) asks if it’s possible to measure exactly z liters using two jugs of capacities x and y liters. We have an infinite water supply and can perform these operations:

Fill one jug completely.
Empty one jug completely.
Pour water from one jug to the other until either the source jug is empty or the target jug is full.

We will discuss three approaches to solve this problem: a Mathematical approach using Bézout's Identity, a Breadth-First Search (BFS) state-space search, and a Depth-First Search (DFS) state-space search. Each approach includes an explanation, step-by-step logic, a Python implementation, and complexity analysis.

1. Mathematical Approach (Bézout's Identity)

How Bézout's Identity Applies

This problem can be solved using number theory. The key observation is that any measurable quantity using the two jugs must be a linear combination of their capacities. Bézout’s identity states that for any integers x and y with greatest common divisor d = gcd(x, y), there exist integers m, n such that m*x + n*y = d. In fact, all integer combinations m*x + n*y are multiples of d.

In the context of the jugs, pouring water between them changes the amounts in each jug but does not create or destroy water – any total amount of water achievable in the jugs must be an integer combination of x and y liters. This means we can measure an amount z if and only if z is a multiple of gcd(x, y). For example, if x=3 and y=5, gcd(3,5)=1, so we can measure any integer amount (in particular 4 liters, as in the famous Die Hard example). But if x=2 and y=6, gcd(2,6)=2 and we cannot measure 5 liters because 5 is not a multiple of 2.

Another obvious necessary condition is that we cannot measure more water than the total capacity of both jugs. If z > x + y, it’s impossible to have z liters in the jugs (they can hold at most x+y when full). Also, if z == 0, the answer is trivially True (zero liters is measurable by doing nothing).

Step-by-Step Logic

Using these observations, we can outline the logic to decide if measurement is possible:

Capacity check: If z > x + y, return False (not enough total capacity to measure z liters).
Trivial cases: If z == 0, return True (no water needed). If x == z or y == z or x + y == z, return True (we can directly fill one or both jugs to reach exactly z).
Compute GCD: Let g = gcd(x, y) – the greatest common divisor of x and y.
Divisibility check: Return True if and only if z is a multiple of g (i.e. z % g == 0); otherwise return False. By Bézout's identity, if z is a multiple of g, there exist some (possibly negative) integers m, n such that m*x + n*y = z, meaning we can achieve exactly z liters through some sequence of fills and pours. If z is not a multiple of g, it’s impossible to measure z liters with these jug sizes.

Python Implementation (Mathematical Solution)

Below is a Python implementation following the above logic. We use the Euclidean algorithm to compute gcd(x, y) efficiently:

def canMeasureWater_math(x: int, y: int, z: int) -> bool:
    # If z is 0, we don't need to do anything
    if z == 0:
        return True
    # If total capacity is less than z, impossible to measure z
    if x + y < z:
        return False
    # If one of the jugs has zero capacity, then we can only measure z if z equals the other jug's capacity
    if x == 0 or y == 0:
        return z == x or z == y

    # Helper function to compute gcd
    def gcd(a, b):
        # Euclidean algorithm
        while b:
            a, b = b, a % b
        return a

    g = gcd(x, y)
    # z must be a multiple of the GCD of x and y
    return z % g == 0

# Examples:
print(canMeasureWater_math(3, 5, 4))  # True, as 4 is measurable
print(canMeasureWater_math(2, 6, 5))  # False, as 5 is not a multiple of gcd(2,6)=2

Time and Space Complexity

Computing the GCD using the Euclidean algorithm takes O(log(min(x, y))) time, which is very fast even for large jug sizes. All other checks are constant time. Therefore, the time complexity of the mathematical approach is O(log(min(x, y))). The space complexity is O(1) (constant space), since we only use a few variables regardless of input size. This approach is extremely efficient for even very large capacities, making it ideal for coding interviews.

2. Breadth-First Search (BFS) Approach

BFS as a State-Space Search

We can model the problem as a state-space search where each state is represented by a pair (a, b) – a liters in jug1 and b liters in jug2. The initial state is (0, 0) (both jugs empty). From any state, we can perform any of the allowed operations to reach a new state. For example, from state (a, b) we can:

Fill Jug1 to its capacity: move to (x, b) (where x is the capacity of jug1).
Fill Jug2 to its capacity: move to (a, y).
Empty Jug1 entirely: move to (0, b).
Empty Jug2 entirely: move to (a, 0).
Pour Jug1 -> Jug2: pour water from jug1 into jug2 until jug1 is empty or jug2 is full. This moves to a state (a - t, b + t) where t = min(a, y - b) (the amount we can pour without overflowing jug2).
Pour Jug2 -> Jug1: pour water from jug2 into jug1 until jug2 is empty or jug1 is full. This moves to (a + t, b - t) where t = min(b, x - a).

These are the state transitions derived from the problem’s allowed operations. BFS will systematically explore all reachable states level by level, using a queue data structure. We start from (0,0) and generate all one-step reachable states, then two-step states, and so on, until we either reach a state where the total water equals z or we exhaust all possibilities.

Why BFS? BFS ensures that if a solution exists, we will find it in the shortest number of steps (operations) because it explores in layers of increasing move count. While the problem only asks for a yes/no answer (not the sequence of steps), BFS is a natural way to explore the search space without getting stuck in loops. We also keep a visited set of states we have seen, to avoid revisiting them and falling into infinite loops (pruning redundant states).

BFS Step-by-Step Logic

Initialize a queue with the start state (0, 0) and a visited set to keep track of seen states.
Process states in BFS order: Repeatedly take the front state from the queue.
- If this state’s jug volumes sum to z (i.e. a + b == z), or one jug alone has z (which implies we can empty the other to get total z), then return True – we found a way to measure z.
- Otherwise, generate all possible next states from the current state (a, b) using the six operations above, and add those states to the queue if they haven’t been visited before.
Mark the current state as visited to avoid re-processing it.
Continue until the queue is empty (no more states to explore). If we exhaust all states without seeing a total of z liters, return False.

Because the state space is finite (there are at most (x+1)*(y+1) possible (a,b) combinations), BFS will eventually terminate. If a solution exists, BFS will find it.

Python Implementation (BFS)

We’ll implement BFS using a queue (collections.deque) and a set for visited states. Each state is a tuple (a, b) of current jug volumes. We check each state and enqueue its neighbors:

from collections import deque

def canMeasureWater_bfs(x: int, y: int, z: int) -> bool:
    if z < 0 or z > x + y:
        # z greater than total capacity or negative z is impossible
        return False
    # Queue for BFS and set for visited states
    queue = deque([(0, 0)])
    visited = set([(0, 0)])
    
    while queue:
        a, b = queue.popleft()
        # Check if we have exactly z liters in total
        if a == z or b == z or a + b == z:
            return True
        # Generate all possible next states from (a, b):
        # 1. Fill jug1 to capacity
        state1 = (x, b)
        # 2. Fill jug2 to capacity
        state2 = (a, y)
        # 3. Empty jug1
        state3 = (0, b)
        # 4. Empty jug2
        state4 = (a, 0)
        # 5. Pour jug1 -> jug2
        transfer = min(a, y - b)
        state5 = (a - transfer, b + transfer)
        # 6. Pour jug2 -> jug1
        transfer = min(b, x - a)
        state6 = (a + transfer, b - transfer)
        for state in [state1, state2, state3, state4, state5, state6]:
            if state not in visited:
                visited.add(state)
                queue.append(state)
    # If queue is empty and we didn't return True, then it's not possible
    return False

# Examples:
print(canMeasureWater_bfs(3, 5, 4))  # True
print(canMeasureWater_bfs(2, 6, 5))  # False

In this code, we check a == z or b == z or a + b == z as the success condition. Checking a + b == z covers cases where the total in both jugs equals z (even if split between jugs). Checking a == z or b == z covers scenarios where one jug alone has z (which implies the other jug can be emptied to achieve exactly z total). Either condition signifies we have measured z liters.

Complexity Analysis (BFS)

Time Complexity: In the worst case, BFS will explore all possible states of the two jugs. There are at most (x+1) * (y+1) distinct states (jug1 can have 0 to x liters, jug2 0 to y liters). Each state generates a constant number (up to 6) of next states. Therefore, the time complexity is O(x * y) in the worst case. This can be large if x and y are big (e.g. if both are on the order of thousands, x*y could be millions of states). However, many states might not be reachable depending on gcd(x,y), and BFS will stop early if a solution is found.

Space Complexity: We store the queue of states and the visited set. In the worst case, the space used is also O(x * y) for the visited states. BFS might use more memory than DFS at peak because it holds all nodes at a given breadth, but it guarantees the shortest solution path (minimal steps) if that is of interest.

3. Depth-First Search (DFS) Approach

Using DFS to Explore States

Like BFS, Depth-First Search will explore the state space of jug configurations, but in a depth-oriented manner. DFS can be implemented recursively or with an explicit stack. The idea is to start from (0,0) and try all possible moves, diving deep into one sequence of moves until we either reach the goal or hit a dead-end, then backtrack. We also use a visited set to prune states we’ve seen before (to avoid infinite loops).

DFS algorithm outline:

Start with a stack (or recursion) containing the initial state (0,0).
Pop the top state (or recursively visit a state).
If it satisfies the goal (a + b == z or one jug equals z), return True.
Otherwise, push all possible next states (that haven’t been visited) onto the stack.
Continue until stack is empty. If no solution found, return False.

DFS will explore one path of moves as far as possible before trying alternate paths. This can sometimes find a solution faster if the correct sequence is deep, but it does not guarantee the shortest solution path in terms of number of operations. In practice, for just determining reachability (yes/no), DFS works as well as BFS as long as we avoid revisiting states.

Python Implementation (DFS)

We implement DFS using a stack for clarity (to avoid Python recursion depth limits). The moves (transitions) are the same as in BFS. We will pop from the stack (LIFO order) to simulate depth-first exploration:

def canMeasureWater_dfs(x: int, y: int, z: int) -> bool:
    if z < 0 or z > x + y:
        return False
    stack = [(0, 0)]
    visited = set([(0, 0)])
    while stack:
        a, b = stack.pop()
        # Check goal
        if a == z or b == z or a + b == z:
            return True
        # Generate next states (same 6 operations as before)
        next_states = []
        next_states.append((x, b))                        # fill jug1
        next_states.append((a, y))                        # fill jug2
        next_states.append((0, b))                        # empty jug1
        next_states.append((a, 0))                        # empty jug2
        transfer = min(a, y - b)                          # pour jug1 -> jug2
        next_states.append((a - transfer, b + transfer))
        transfer = min(b, x - a)                          # pour jug2 -> jug1
        next_states.append((a + transfer, b - transfer))
        # Push unvisited next states onto stack
        for state in next_states:
            if state not in visited:
                visited.add(state)
                stack.append(state)
    return False

# Examples:
print(canMeasureWater_dfs(3, 5, 4))  # True
print(canMeasureWater_dfs(2, 6, 5))  # False

This DFS implementation is very similar to BFS except that it uses a stack (LIFO) instead of a queue. It will explore one sequence of moves completely before exploring another. We still mark visited states to avoid repetition.

Trade-offs Compared to BFS

Shortest Path vs Any Path: BFS finds the minimum number of operations needed to reach the solution (if required), whereas DFS might find a solution via a longer sequence of pours first. For this problem, we only care about existence, not the shortest sequence, so DFS is acceptable. But if we needed the minimum steps, BFS is the better choice.
Memory Usage: DFS tends to use less memory at any one time than BFS. BFS stores an entire layer of states in the queue, which could be a lot, whereas DFS essentially stores just the current path (and the visited set common to both). However, both ultimately may need to mark all states as visited in the worst case, which is O(x*y) space for the visited set.
Performance: In terms of time complexity, DFS will also potentially explore all states in the worst case, which is O(x * y) like BFS. With proper pruning (visited-check), DFS will not repeat states, so it won’t go into an infinite loop. Without pruning, DFS could get stuck bouncing between states indefinitely, so the visited set is crucial for efficiency and termination. With pruning, both DFS and BFS will examine each reachable state at most once.
Implementation simplicity: DFS can be implemented recursively in a very straightforward manner, which some find easier to understand. BFS requires an explicit queue. In our solution we used an explicit stack for DFS to mirror BFS logic and avoid deep recursion, but conceptually DFS could be shown with recursion as well.

In summary, DFS is an alternative that explores the state space differently. It will find a solution if one exists, but it may traverse a longer path first. BFS is usually preferred for puzzle problems like this when we want the shortest solution or to systematically ensure finding a solution without getting lost deep in one branch. Nonetheless, both approaches have the same worst-case complexity and will solve the problem for reasonable jug sizes.

Time and Space Complexity (DFS)

With the visited set, DFS will also visit each state at most once, giving a worst-case time complexity of O(x * y) (same as BFS). The space complexity is also O(x * y) due to the visited set. The call stack (or explicit stack) in DFS can grow up to the number of states in the worst case as well, though typically it will be at most the depth of the state graph. In practice, the mathematical GCD method is far more efficient for large inputs, but BFS/DFS are useful to understand for small jugs or for demonstrating the solution path.

Conclusion

For the Water and Jug problem, the mathematical (Bézout's identity) solution is the most efficient way to determine reachability of exactly z liters – it runs in essentially constant time by checking the GCD condition. The BFS and DFS approaches treat the problem as a graph of states and use graph search to find a solution. BFS explores level by level and guarantees the shortest sequence of operations if needed, while DFS explores more like backtracking. Both require careful handling of visited states to avoid infinite loops. For interview preparation, it’s good to understand all three approaches: the GCD method for its elegance and efficiency, and BFS/DFS to demonstrate problem modeling and search algorithm knowledge. Each approach arrives at the same correctness criterion – that a solution exists if z is not more than total capacity and is divisible by gcd(x, y) – but via different reasoning techniques.