From 9549dbb2666e1032ad1f55218e68fd7ac636485e Mon Sep 17 00:00:00 2001 From: William Carroll Date: Mon, 23 Nov 2020 23:21:20 +0000 Subject: Update BFS impls I've subtly been implementing breadth-first traversals in graphs incorrectly. The change is subtle, but updating `seen` needs to happen immediately after queuing an item. The results will remain the same, but the runtimes will differ dramatically. I didn't notice this until I attempted to complete LeetCode's "count islands" challenge, and LeetCode rejected my solution because it could not finish before timing out. After looking at other candidates' solutions and comparing them to mine, I couldn't see any difference... except for this subtle difference. This SO answer provides a helpful explanation: https://stackoverflow.com/questions/45623722/marking-node-as-visited-on-bfs-when-dequeuing The take-away lesson here is to always call `seen.add(..)` immediately after enqueuing. --- scratch/facebook/count-islands.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'scratch/facebook/count-islands.py') diff --git a/scratch/facebook/count-islands.py b/scratch/facebook/count-islands.py index a007684bca23..b876319b2f7a 100644 --- a/scratch/facebook/count-islands.py +++ b/scratch/facebook/count-islands.py @@ -8,6 +8,7 @@ def maybe_queue(row, col, game, q, seen): if row >= 0 and row < len(game) and col >= 0 and col < len(game[0]): if game[row][col] == 'L' and (row, col) not in seen: q.append((row, col)) + seen.add((row, col)) def visit_island(row, col, game, seen): """ @@ -18,7 +19,6 @@ def visit_island(row, col, game, seen): q.append((row, col)) while q: row, col = q.popleft() - seen.add((row, col)) maybe_queue(row - 1, col, game, q, seen) # UP maybe_queue(row + 1, col, game, q, seen) # DOWN maybe_queue(row, col - 1, game, q, seen) # LEFT -- cgit 1.4.1