Building H2o - Leetcode Solution

Problem statement:

You are given two empty jugs with capacities jug1Capacity and jug2Capacity respectively, and an integer targetCapacity.

The rules are:

• You can pour any amount of water into a jug at a time.
• You can empty a jug at any time.
• You can only pour water from one jug into another jug.
• You cannot pour more water into a jug than its capacity, eg. if jug1Capacity = 3, you cannot pour 5 units of water into jug1.

Write a function that returns true if it is possible to measure exactly targetCapacity litres using these two jugs, otherwise false.

Solution:

To solve this problem, we will use a variation of the Breadth First Search (BFS) algorithm. The idea is to represent every state as a tuple (x, y) where x and y represent the levels of water in jug1 and jug2, respectively.

We will also keep a set of visited states to avoid visiting the same state again.

The algorithm will start by adding the initial state (0, 0) to a queue.

Then, we will loop through the queue until it is empty. At each iteration, we will pop a state from the queue and generate all possible states that can be reached from that state.

To generate the possible states, we will try every combination of pouring water from one jug to another or emptying one jug.

If a generated state has not been visited before, we will add it to the queue and mark it as visited. We will also check if the generated state has a level of water that matches the targetCapacity. If it does, we return true.

If we reach the end of the loop and have not found a state that matches the targetCapacity, we return false.

Let's see the code implementation:

def canMeasureWater(jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
    # set up visited states set and queue
    visited = set()
    queue = [(0, 0)]
    
    # loop through queue until empty
    while queue:
        # pop state from queue
        state = queue.pop(0)
        x, y = state
        
        # check if state matches targetCapacity
        if x + y == targetCapacity:
            return True
        
        # generate possible states
        possible_states = [
            (0, y),                          # empty jug1
            (x, 0),                          # empty jug2
            (jug1Capacity, y),               # fill jug1
            (x, jug2Capacity),               # fill jug2
            (x + min(x+y, jug2Capacity-y),   # pour from jug1 to jug2
             y - min(x+y, jug2Capacity-y)),
            (x - min(x+y, jug1Capacity-x),   # pour from jug2 to jug1
             y + min(x+y, jug1Capacity-x))
        ]
        
        # loop through possible_states
        for s in possible_states:
            # check if state has not been visited
            if s not in visited:
                # add state to queue and visited set
                visited.add(s)
                queue.append(s)
    
    # reached end of loop without finding targetCapacity
    return False

The time complexity of this algorithm is O(jug1Capacity * jug2Capacity) since there can be jug1Capacity * jug2Capacity possible states. The space complexity is also O(jug1Capacity * jug2Capacity) since we need to keep track of the visited states.

1