about summary refs log tree commit diff
path: root/playbooks/finances.org
diff options
context:
space:
mode:
authorWilliam Carroll <wpcarro@gmail.com>2020-11-23T23·21+0000
committerWilliam Carroll <wpcarro@gmail.com>2020-11-23T23·21+0000
commit9549dbb2666e1032ad1f55218e68fd7ac636485e (patch)
tree70c089928040ed103dc567de3f2a99c5804ac5ea /playbooks/finances.org
parentc00eed469ccd5f4b53d98ceeeba32963dd593ed8 (diff)
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.
Diffstat (limited to 'playbooks/finances.org')
0 files changed, 0 insertions, 0 deletions