Bus Routes


  • 0

    Click here to see the full article post


  • 0
    E

    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).


  • 1
    P

    @EatSleepLeetCode There are N nodes, each node could have N edges. Max total edges = N^2.


  • 1
    P

    @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).


  • 0
    E

    @pedro Thank you so much!


  • 0
    W

    Number of bus could more than number of node this way may be slow than using node do bfs. And bidirectional search maybe better.


  • 0
    S

    Creating graph can be done faster by first creating bus stop to list of bus mapping. Then for each bus, we can connect it with other buses by this mapping. And the total time to construct graph is O(sigma(bus_i))


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.