Click here to see the full article post
Thanks for posting the solution. I have confusion regarding time complexity for BFS. Shouldn't it be O(N + N) i.e. N nodes and N edges i.e. O(N). I am not sure why is it O(N^2).
@EatSleepLeetCode There are N nodes, each node could have N edges. Max total edges = N^2.
@EatSleepLeetCode btw, in python the work to create the graph is O(N^3) - that's what the summation boils down to in the worst case - which dominates the time spent in the BFS actually.
If you pre-process to get a map from stop -> bus route in O(N^2), we can still do a BFS on the stops that is O(N^2), making it significantly faster. Keep track of visited bus stops and visited bus routes. Whenever you visit a stop, for each bus you have not used that goes to that stop, add all the unvisited stops from that bus route to the queue.
On each stop you'll have to consider all the bus routes which is O(N) per stop or O(N^2) total and since you only have to look at the stops on a given bus route once, the total work is O(N^2).
@pedro Thank you so much!
Number of bus could more than number of node this way may be slow than using node do bfs. And bidirectional search maybe better.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.