815. Bus Routes

Bus Routes (LeetCode 815) 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.

How to solve Bus Routes

Bus Routes is a Bidirectional BFS Optimization problem, part of Graph Traversal Patterns (DFS & BFS). Optimize BFS by searching from both source and target simultaneously. Reduce time complexity significantly.

Work towards the solution in these steps:

1. Think about modeling the problem as a graph traversal, where nodes could represent either bus stops or bus routes.
2. Consider how to represent connections efficiently: buses are connected if they share at least one common stop, and stops connect to the buses that serve them.
3. Use BFS to find the shortest path in terms of bus transfers from the source stop to the target stop, starting from all buses that include the source.

The reference solution runs in O(|V| + |E|) time and O(|V| + |E|) space.

The Bus Routes solution and editorial walks through the full approach with reference code.

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 <= 10^5 - All the values of routes[i] are unique. - sum(routes[i].length) <= 10^5 - 0 <= routes[i][j] < 10^6 - 0 <= source, target < 10^6

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

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:

• Open the Lock — Medium, same subpattern
• 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

Bus Routes FAQ