Solve Multiple Coding Interview Problems

Problem Statement

You are given an array of transit routes routes where routes[i] is a list of stop IDs that transit vehicle i visits repeatedly in a loop. For example, if routes[0] = [1, 5, 7], transit vehicle 0 visits stop 1, then stop 5, then stop 7, then stop 1, and so on.

You start at stop source and want to reach stop target. You can transfer between any two transit routes at any stop that is shared by both routes. You start with no vehicle boarded.

Return the minimum number of transit lines you must take to travel from source to target. If it is impossible to reach target from source, return -1.

Function Signature

def min_transit_routes(routes: list[list[int]], source: int, target: int) -> int:
    pass

Input and Output Format

• Input:
  • routes: A list of lists of integers, where each inner list represents the sequence of stops for a single transit line.
  • source: An integer denoting the starting stop ID.
  • target: An integer denoting the destination stop ID.
• Output: An integer representing the minimum number of transit routes taken, or -1 if unreachable.

Constraints

• 1 <= len(routes) <= 500
• 1 <= len(routes[i]) <= 10^5
• sum(len(routes[i])) <= 10^5
• 0 <= routes[i][j] < 10^6
• All stops in a single route routes[i] are unique.
• 0 <= source, target < 10^6

Examples

Example 1

routes = [[1, 2, 7], [3, 6, 7]]
source = 1
target = 6
# Output: 2

Explanation: You can board route 0 at stop 1, ride it to stop 7, switch to route 1 at stop 7, and ride route 1 to stop 6. You take 2 transit lines in total.

Example 2

routes = [[7, 12], [4, 5, 15], [6], [15, 19], [9, 12, 13]]
source = 15
target = 12
# Output: -1

Explanation: There is no sequence of transfers connecting stop 15 to stop 12.

Edge Cases to Consider

• source == target: You are already at the destination, so the answer is 0.
• source or target does not appear in any route: Return -1.
• Disconnected transit components where target is isolated from source.