LeetCode 365: Water and Jug Problem Solution in Python – A Step-by-Step Guide

What Is LeetCode 365: Water and Jug Problem?

LeetCode 365: Water and Jug Problem gives you two jugs with capacities x and y, and a target amount z. You can fill, empty, or pour water between them, and the goal is to determine if it’s possible to measure exactly z liters using these operations. It’s a classic problem rooted in number theory and state exploration!

Problem Statement

• Input:
• jug1Capacity (x): Integer capacity of the first jug.
• jug2Capacity (y): Integer capacity of the second jug.
• targetCapacity (z): Integer target amount to measure.
• Output: Boolean - True if z can be measured, False otherwise.
• Rules:
• Operations: Fill a jug, empty a jug, pour water from one jug to another.
• Measure z using the total water in either or both jugs.

Constraints

• 1 <= jug1Capacity, jug2Capacity <= 10⁶
• 0 <= targetCapacity <= 10⁶

Examples

• Input: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
• Output: True
• Fill 5L jug → (0,5), pour to 3L jug → (3,2), empty 3L → (0,2), pour 5L to 3L → (2,0), fill 5L → (2,5), pour to 3L → (3,4). Total = 4.
• Input: jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5
• Output: False
• Possible sums are multiples of 2 (GCD), 5 is odd, impossible.
• Input: jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3
• Output: True
• Fill 1L → (1,0), pour to 2L → (0,1), fill 1L → (1,1), pour to 2L → (0,2), fill 1L → (1,2). Total = 3.

These show the interplay of jug sizes—let’s solve it!

Understanding the Problem: Measuring Water

To tackle LeetCode 365 in Python, we need to: 1. Determine if z can be achieved using fill, empty, and pour operations. 2. Account for jug capacities x and y. 3. Ensure z is measurable as a total in one or both jugs.

A naive approach might simulate all operations, but we can use math or search. We’ll explore:

• Best Solution: Bézout’s identity with GCD—O(log(min(x,y))) time, O(1) space—fast and elegant.
• Alternative Solution: BFS—O(x*y) time, O(x*y) space—intuitive but slower.

Let’s measure with the best solution!

Best Solution: Bézout’s Identity with GCD

Why This Is the Best Solution

The Bézout’s identity approach runs in O(log(min(x,y))) time by using number theory: any amount measurable is a multiple of the greatest common divisor (GCD) of x and y, and z must be ≤ x + y and satisfy Bézout’s equation (ax + by = z). It’s the most efficient—avoiding exhaustive state exploration!

How It Works

Think of it like a math trick:

• Bézout’s Identity: For integers a and b, if z = ax + by, then z must be a multiple of gcd(x,y).
• Conditions:
• z ≤ x + y (total capacity).
• z % gcd(x,y) == 0 (must be achievable).
• GCD: Compute using Euclidean algorithm.
• Result: True if conditions hold, False otherwise.

It’s like finding the rhythm of pourable amounts!

Step-by-Step Example

For x=3, y=5, z=4:

• GCD: gcd(3,5) = 1 (3,5 are coprime).
• Check:
• z=4 ≤ 3+5=8 ✓.
• 4 % 1 = 0 ✓.
• Bézout: 4 = 3*(-2) + 5*2 (possible with negative a, b allowed in theory).
• Result: True (operations exist: e.g., fill 5, pour to 3, empty 3, pour 2 to 3, fill 5, pour to 3 → (3,4)).

For x=2, y=6, z=5:

• GCD: gcd(2,6) = 2.
• Check:
• 5 ≤ 2+6=8 ✓.
• 5 % 2 = 1 ≠ 0 ✗.
• Result: False (only multiples of 2 possible).

Code with Explanation

Here’s the Python code using GCD:

Copy codeclass Solution:
    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
        # Helper to compute GCD using Euclidean algorithm
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a

        x, y, z = jug1Capacity, jug2Capacity, targetCapacity

        # Check basic conditions
        if z > x + y:  # Target exceeds total capacity
            return False
        if z == 0:  # Empty is always possible
            return True
        if x == 0 or y == 0:  # One jug empty
            return z == 0 or z == max(x, y)

        # Check if z is a multiple of gcd(x, y)
        return z % gcd(x, y) == 0

Explanation

• Lines 3-7: gcd: Euclidean algorithm—e.g., gcd(3,5): 5%3=2, 3%2=1, 2%1=0 → 1.
• Line 10: Rename for clarity: x=jug1, y=jug2, z=target.
• Lines 12-16: Base cases:
• z > x + y: Impossible if target exceeds total.
• z = 0: True (empty state).
• x or y = 0: True only if z = 0 or z = other jug’s capacity.
• Line 18: Core check: z must be a multiple of gcd(x,y) per Bézout’s identity.

• Time Complexity: O(log(min(x,y)))—GCD computation.
• Space Complexity: O(1)—no extra space.

This is like a mathematical water key—unlock the solution fast!

Alternative Solution: BFS

Why an Alternative Approach?

The BFS (Breadth-First Search) solution runs in O(x*y) time by exploring all possible states of the jugs. It’s slower but explicitly simulates operations—great for understanding the process or verifying the math!

How It Works

• States: Track (jug1, jug2) water amounts.
• BFS: Use a queue to explore states via fill, empty, pour.
• Check: If total water = z, return True.

Step-by-Step Example

For x=3, y=5, z=4:

• Init: Queue = [(0,0)], Seen = {(0,0)}.
• (0,0):
• Fill 3L: (3,0) → Queue, Seen.
• Fill 5L: (0,5) → Queue, Seen.
• (3,0):
• Pour 3L→5L: (0,3).
• Total=3 < 4.
• (0,5):
• Pour 5L→3L: (3,2).
• Total=5 > 4.
• (3,2):
• Total=5 > 4.
• Empty 3L: (0,2).
• (0,2):
• Fill 3L: (3,2).
• Total=2 < 4.
• (3,2):
• Pour 3L→5L: (0,5) (seen).
• Pour 5L→3L: (3,4).
• (3,4):
• Total=7 > 4.
• Empty 3L: (0,4).
• (0,4):
• Total=4 ✓, return True.

Code with Explanation

Copy codefrom collections import deque

class Solution:
    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
        x, y, z = jug1Capacity, jug2Capacity, targetCapacity

        if z > x + y:
            return False
        if z == 0:
            return True

        # BFS with state (jug1, jug2)
        queue = deque([(0, 0)])
        seen = {(0, 0)}

        while queue:
            j1, j2 = queue.popleft()
            total = j1 + j2

            if total == z:
                return True

            # Possible operations
            states = [
                (x, j2),  # Fill jug1
                (j1, y),  # Fill jug2
                (0, j2),  # Empty jug1
                (j1, 0),  # Empty jug2
                # Pour jug1 to jug2
                (j1 - min(j1, y - j2), j2 + min(j1, y - j2)),
                # Pour jug2 to jug1
                (j1 + min(j2, x - j1), j2 - min(j2, x - j1))
            ]

            for next_j1, next_j2 in states:
                if 0 <= next_j1 <= x and 0 <= next_j2 <= y and (next_j1, next_j2) not in seen:
                    queue.append((next_j1, next_j2))
                    seen.add((next_j1, next_j2))

        return False

Explanation

• Lines 7-11: Base cases: z > total capacity or z = 0.
• Lines 13-14: Start BFS with (0,0) state.
• Lines 16-34: BFS loop:
• Pop current state, check if total = z.
• Generate next states: fill, empty, pour (calculate water transfer).
• Add valid unseen states to queue.
• Time: O(x*y)—number of possible states.
• Space: O(x*y)—queue and seen set.

It’s like exploring all water paths!

Comparing the Two Solutions

• Bézout’s Identity with GCD (Best):
• Time: O(log(min(x,y)))—GCD computation.
• Space: O(1)—minimal.
• Pros: Super fast, elegant.
• Cons: Requires math insight.
• BFS (Alternative):
• Time: O(x*y)—state exploration.
• Space: O(x*y)—queue and set.
• Pros: Explicit, verifiable.
• Cons: Slow for large capacities.

GCD wins for efficiency!

Additional Examples and Edge Cases

• x=1, y=1, z=1: True.
• x=0, y=5, z=5: True.
• x=2, y=4, z=3: False.

Both handle these, GCD is faster.

Complexity Breakdown

• GCD:
• Time: O(log(min(x,y))).
• Space: O(1).
• BFS:
• Time: O(x*y).
• Space: O(x*y).

GCD excels for speed.

Key Takeaways

• GCD: Math solves it—fast and smart!
• BFS: Explore all paths—clear and thorough!
• Jugs: Logic meets practice.
• Python Tip: Math and queues rock—see [Python Basics](/python/basics).

Final Thoughts: Measure That Water

LeetCode 365: Water and Jug Problem in Python is a jug-juggling challenge. GCD with Bézout’s identity is the efficiency champ, while BFS builds intuition. Want more? Try LeetCode 279: Perfect Squares or LeetCode 373: Find K Pairs with Smallest Sums. Ready to pour? Visit Solve LeetCode 365 on LeetCode and measure that water today!