Approach #1: Breadth First Search [Accepted]
Intuition
Instead of thinking of the stops as nodes (of a graph), think of the buses as nodes. We want to take the least number of buses, which is a shortest path problem, conducive to using a breadthfirst search.
Algorithm
We perform a breadth first search on bus numbers. When we start at S
, originally we might be able to board many buses, and if we end at T
we may have many targets
for our goal state.
One difficulty is to efficiently decide whether two buses are connected by an edge. They are connected if they share at least one bus stop. Whether two lists share a common value can be done by set intersection (HashSet), or by sorting each list and using a two pointer approach.
To make our search easy, we will annotate the depth of each node: info[0] = node, info[1] = depth
.
Complexity Analysis

Time Complexity: Let denote the number of buses, and be the number of stops on the th bus.

To create the graph, in Python we do work (we can improve this by checking for which of
r1, r2
is smaller), while in Java we did a sorting step, plus our searches are work. 
Our (breadthfirst) search is on nodes, and each node could have edges, so it is .


Space Complexity: additional space complexity, the size of
graph
androutes
. In Java, our space complexity is because we do not have an equivalent ofroutes
. Dualpivot quicksort (as used inArrays.sort(int[])
) is an inplace algorithm, so in Java we did not increase our space complexity by sorting.
Analysis written by: @awice.