Bus Routes
Bus Routes is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Bidirectional BFS (BFS optimization for known source & target) subpattern.
Problem statement
You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.
For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.
You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.
Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.
Example 1: Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6 Output: 2 Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Example 2: Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 Output: -1
Constraints: 1 <= routes.length <= 500.
1 <= routes[i].length <= 105 All the values of routes[i] are unique.
sum(routes[i].length) <= 105 0 <= routes[i][j] < 106 0 <= source, target < 106
Topics and companies
Topics: Breadth-first Search.
Reported in interviews at Amazon, Square, Uber.
How to practise Bus Routes on Thita.ai
Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(|V| + |E|) time and O(|V| + |E|) space.
Open Bus Routes in the code editor, or read the Bus Routes editorial for a worked solution with its approach and complexity analysis.
Where Bus Routes sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Bidirectional BFS (BFS optimization for known source & target) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Bus Routes
Other problems that use the same Bidirectional BFS (BFS optimization for known source & target) and Graph Traversal Patterns (DFS & BFS) techniques:
- Word Ladder II — Hard, same subpattern
- Accounts Merge — Medium, same pattern
- Alien Dictionary — Hard, same pattern
- All Paths from Source Lead to Destination — Medium, same pattern
- Build a Matrix With Conditions — Hard, same pattern
- Cheapest Flights Within K Stops — Medium, same pattern