Bus Routes · Interview Problem

Back to problems

Leetcode

bus-routes

Medium

Graphs

Hash Maps

Breadth-First Search

Bus Routes

Given a list of bus routes, find the minimum number of buses one must take to travel from a source to a target stop.

Acceptance 33%

Start Practice

Problem Statement

Core description from the backend problem record.

Description

You are given an array routes representing bus routes where routes[i] is a list of stops that the i-th bus repeats forever.

You start at the source bus stop and want to go to the target bus stop. You can get on any bus at any stop on its route. Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible to reach the target bus stop from the source.

Input Format

routes: List[List[int]] representing bus routes
source: int representing starting bus stop
target: int representing destination bus stop

Output Format

int representing the minimum number of buses to take, or -1 if impossible

Constraints

1 <= routes.length <= 500
1 <= routes[i].length <= 10^5
0 <= routes[i][j], source, target < 10^6

Loading Preptin

Description

Input Format

Output Format

Constraints