Leetcode 752: Open the Lock TLE with BFS

user_5330107 0
Viewed 56

I'm trying to solve the leetcode question https://leetcode.com/problems/open-the-lock/ with BFS and came up with the approach below.

def openLock(self, deadends: List[str], target: str): -> int
      def getNeighbors(node) ->List[str]:
            neighbors = []
            dirs = [-1, 1]
            for i in range(len(node)):
                for direction in dirs:
                    x = (int(node[i]) + direction) % 10
                    neighbors.append(node[:i] + str(x) + node[i+1:])
            return neighbors
                        
        start = '0000'
        if start in deadends:
            return -1
        queue = deque()
        queue.append((start, 0))
        turns = 0
        visited = set()
        deadends = set(deadends)
        while queue:
            state, turns = queue.popleft()
            visited.add(state)
            if state == target:
                return turns
            for nb in getNeighbors(state):
                if nb not in visited and nb not in deadends:   
                    queue.append((nb, turns+1))
        return -1

However this code runs into a Time Limit Exceeded exception and it only passes 2/48 of the test cases. For ex. with a testcase where the deadends are ["8887","8889","8878","8898","8788","8988","7888","9888"] and the target is "8888" (the start is always "0000") my solution TLE. I notice that if I essentially change one line and add neighboring nodes to the visited set in my inner loop, my solution passes that test case and all other test cases.

for nb in getNeighbors(state):
     if nb not in visited and nb not in deadends:   
         visited.add(nb)
         queue.append((nb, turns+1))

My while loop then becomes

while queue:
            state, turns = queue.popleft()
            if state == target:
                return turns
            for nb in getNeighbors(state):
                if nb not in visited and nb not in deadends:   
                    visited.add(nb)
                    queue.append((nb, turns+1))

Can someone explain why the first approach runs into TLE while the second doesn't?

breadth-first-search python
2 Answers

Yes. Absolutely. You need to add the item to visited when it gets added to the queue the first time, not when it gets removed from the queue. Otherwise your queue is going to grow exponentially.

Let's look at say 1111. Your code is going to add 1000, 0100, 0010, 0001 (and others) to the queue. Then your code is going to add each of 1100, 1010, 1001, 0110, 0101, 0011, and others twice because they are neighbors of two elements in the queue, and they haven't been visited yet. And then you add each of 1110, 1101, 1011, 0111 four times. If instead you're searching for 5555, you'll have many many duplicates on your queue.

Change the name of your visited variable to seen. Notice that once an item has been put on the queue, it never needs to be put on the queue again.

Seriously, try searching for 5555 with no dead ends. When you find it, look at the queue and see how many elements are on the queue, versus how many distinct elements are on the queue.

user_64574070

You are adding next states to try (neighboring states) to the queue, but since you only check if new states have either already been visited, or are dead ends, you end up adding states you haven't tried yet to the queue many times. (i.e. you have no way of telling if a new state was already queued)

Basically, you're getting a bit too fancy here. A simpler implementation of the same idea:

def openLock(dead_ends: list[str], target: str, start: str = '0000') -> int:
    # you could create locks with hexadecimal, alphabetic etc. disks
    symbols = list(map(str, [*range(10)]))  
    if start in dead_ends or target in dead_ends:
        return -1
    elif start == target:
        return 0
    assert all(l == len(start) == len(target) for l in map(len, dead_ends)), \
        'length of start, target and dead ends must match'
    assert all(all(s in symbols for s in code) for code in dead_ends + [start, target]), \
        f'all symbols in start, target and dead ends must be in {symbols}'

    try_neighbors = [start]
    tries = {start: 0}
    while try_neighbors:
        state = try_neighbors.pop(0)
        for i, s in enumerate(state):
            for step in (-1, +1):
                neighbor = state[:i] + symbols[(symbols.index(s) + step) % len(symbols)] + state[i+1:]
                if neighbor in tries:
                    continue
                if neighbor == target:
                    return tries[state] + 1
                elif neighbor not in dead_ends:
                    tries[neighbor] = tries[state] + 1
                    try_neighbors.append(neighbor)
    return -1


# Provides the answer `-1` because it cannot be solved.
print(openLock(["8887","8889","8878","8898","8788","8988","7888","9888"], "8888"))

# Provides the answer `8` steps
print(openLock(["8887","8889","8878","8898","8788","8988","7888"], "8888"))

Your own solution with the problems fixed:

from collections import deque


def openLock(deadends: list[str], target: str) -> int:
    def getNeighbors(node) -> list[str]:
        neighbors = []
        dirs = [-1, 1]
        for i in range(len(node)):
            for direction in dirs:
                x = (int(node[i]) + direction) % 10
                neighbors.append(node[:i] + str(x) + node[i + 1:])
        return neighbors

    start = '0000'
    if start in deadends:
        return -1
    queue = deque()
    queue.append((start, 0))
    # keep track of all you've seen
    seen = set()
    deadends = set(deadends)
    while queue:
        state, turns = queue.popleft()
        seen.add(state)
        for nb in getNeighbors(state):
            # why wait for it to come up in the queue?
            if nb == target:
                return turns + 1
            if nb not in seen and nb not in deadends:
                queue.append((nb, turns + 1))
                # add everything you've queued up to seen
                seen.add(nb)
    return -1


print(openLock(["8887","8889","8878","8898","8788","8988","7888","9888"], "8888"))
user_43901600
Related