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 breadth-first 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 (breadth-first) search is on nodes, and each node could have edges, so it is .

  • Space Complexity: additional space complexity, the size of graph and routes. In Java, our space complexity is because we do not have an equivalent of routes. Dual-pivot quicksort (as used in Arrays.sort(int[])) is an in-place algorithm, so in Java we did not increase our space complexity by sorting.


Analysis written by: @awice.