How hard is LeetCode 365. Water and Jug Problem?

LeetCode 365. Water and Jug Problem is rated Medium on LeetCode.

What is the time complexity of LeetCode 365. Water and Jug Problem?

The Python solution on this page runs in O(x + y).

What is the space complexity of LeetCode 365. Water and Jug Problem?

The Python solution on this page uses O(x + y) auxiliary space.

What topics does LeetCode 365. Water and Jug Problem cover?

LeetCode 365. Water and Jug Problem is tagged Depth-First Search, Breadth-First Search and Math on LeetCode.

Water and Jug Problem — LeetCode 365 Python Solution

MediumDepth-First SearchBreadth-First SearchMath

Problem: #365
Pattern: Breadth-First Search
Reading time: 3 min
Source: leetcode.com

The problem

You are given two jugs with capacities x liters and y liters. You have an infinite water supply.

Python solution

Python

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        def dfs(i: int, j: int) -> bool:
            if (i, j) in vis:
                return False
            vis.add((i, j))
            if i == z or j == z or i + j == z:
                return True
            if dfs(x, j) or dfs(i, y) or dfs(0, j) or dfs(i, 0):
                return True
            a = min(i, y - j)
            b = min(j, x - i)
            return dfs(i - a, j + a) or dfs(i + b, j - b)

        vis = set()
        return dfs(0, 0)

Complexity

Measure	Complexity
Time	O(x + y)
Space	O(x + y) auxiliary

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 365. Water and Jug Problem is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 365. Water and Jug Problem?: LeetCode 365. Water and Jug Problem is rated Medium on LeetCode.
What is the time complexity of LeetCode 365. Water and Jug Problem?: The Python solution on this page runs in O(x + y).
What is the space complexity of LeetCode 365. Water and Jug Problem?: The Python solution on this page uses O(x + y) auxiliary space.
What topics does LeetCode 365. Water and Jug Problem cover?: LeetCode 365. Water and Jug Problem is tagged Depth-First Search, Breadth-First Search and Math on LeetCode.