Bus Routes

HardGraphsbfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given routes, where routes[i] lists the bus stops that bus i visits, repeating forever in a loop. You can ride a bus between any two stops on its route, and you can switch between buses at any stop they share. You start at stop source (not on any bus yet) and want to reach stop target. Return the minimum number of **buses** you must board, or -1 if the target cannot be reached. If source == target, the answer is 0 even if that stop is on no route. Aim for time roughly linear in the total number of stops listed across all routes.

Examples

Input: routes = [[1,4,9],[9,12,20],[20,5]], source = 1, target = 5
Output: 3
Ride bus 0 from 1 to 9, bus 1 from 9 to 20, then bus 2 from 20 to 5.
Input: routes = [[2,3],[8,9]], source = 2, target = 9
Output: -1
The two buses share no stop, so you can never transfer.

Constraints

  • 1 <= routes.length <= 500
  • 1 <= routes[i].length <= 10^5 and the total of all routes[i].length <= 10^5
  • The stops within one route are distinct
  • 0 <= routes[i][j], source, target < 10^6

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bfs problems