Bus Routes - Practice Coding Problems

Bus Routes - Problem

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

For example, if routes[0] = [1, 5, 7], this means that the 0-th 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.

Input & Output

Example 1 — Basic Transfer

$ Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6

› Output: 2

💡 Note: Take Bus 0 from stop 1 to stop 7, then transfer to Bus 1 from stop 7 to reach stop 6. Total: 2 buses.

Example 2 — Direct Route

$ Input: routes = [[7,12],[4,5,15],[6],[15,19,26,7]], source = 15, target = 12

› Output: -1

💡 Note: No possible route from stop 15 to stop 12. Bus 1 contains 15, Bus 0 contains 12, but they don't share any common stops.

Example 3 — Same Stop

$ Input: routes = [[1,2,7],[3,6,7]], source = 6, target = 6

› Output: 0

💡 Note: Already at target stop, no buses needed.

Constraints

1 ≤ routes.length ≤ 500
1 ≤ routes[i].length ≤ 10⁵
All the values of routes[i] are unique
sum(routes[i].length) ≤ 10⁵
0 ≤ routes[i][j] < 10⁶
0 ≤ source, target < 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Bus routes and source/target stops

Process

Find minimum bus transfers using BFS

Output

Minimum number of buses needed

Key Takeaway

🎯 Key Insight: Think in terms of buses as graph nodes rather than individual stops - BFS on buses finds optimal transfer count

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to model this as a graph problem where buses are nodes, not stops. Use BFS on buses to find the minimum transfers. Build a stop→buses mapping first, then explore buses level by level. Best approach is BFS with Time: O(N×M), Space: O(N×M).

Common Approaches

Approach	Time	Space	Notes
✓ BFS (Optimal)	O(N × M)	O(N × M)	Use breadth-first search to find minimum number of bus transfers
Brute Force DFS	O(2^n)	O(n)	Try all possible combinations of bus routes using depth-first search

BFS (Optimal) — Algorithm Steps

Step 1: Create a map from each stop to all buses that visit it
Step 2: Start BFS from all buses that contain the source stop
Step 3: For each bus, explore all its stops and queue new reachable buses
Step 4: Return the level when target is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Map Building

Create stop→buses mapping for quick lookup

BFS Queue

Start with buses containing source, explore level by level

Optimal Result

First time target is found gives minimum transfers

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_BUSES 500
#define MAX_STOPS 1000000
#define MAX_QUEUE 10000

typedef struct {
    int bus;
    int transfers;
} QueueItem;

int solution(int routes[][100], int routeSizes[], int numRoutes, int source, int target) {
    if (source == target) return 0;
    
    // Simple BFS implementation
    QueueItem queue[MAX_QUEUE];
    int front = 0, rear = 0;
    int visitedBuses[MAX_BUSES] = {0};
    
    // Find buses containing source
    for (int i = 0; i < numRoutes; i++) {
        for (int j = 0; j < routeSizes[i]; j++) {
            if (routes[i][j] == source) {
                queue[rear].bus = i;
                queue[rear].transfers = 1;
                rear++;
                visitedBuses[i] = 1;
                break;
            }
        }
    }
    
    while (front < rear) {
        QueueItem current = queue[front++];
        
        // Check all stops on current bus
        for (int i = 0; i < routeSizes[current.bus]; i++) {
            int stop = routes[current.bus][i];
            if (stop == target) {
                return current.transfers;
            }
            
            // Find other buses that visit this stop
            for (int j = 0; j < numRoutes; j++) {
                if (!visitedBuses[j]) {
                    for (int k = 0; k < routeSizes[j]; k++) {
                        if (routes[j][k] == stop) {
                            visitedBuses[j] = 1;
                            queue[rear].bus = j;
                            queue[rear].transfers = current.transfers + 1;
                            rear++;
                            break;
                        }
                    }
                }
            }
        }
    }
    
    return -1;
}

int main() {
    int routes[100][100];
    int routeSizes[100];
    int numRoutes = 2;
    int source, target;
    
    scanf("%d", &source);
    scanf("%d", &target);
    
    // Simplified parsing
    routes[0][0] = 1; routes[0][1] = 2; routes[0][2] = 7; routeSizes[0] = 3;
    routes[1][0] = 3; routes[1][1] = 6; routes[1][2] = 7; routeSizes[1] = 3;
    
    int result = solution(routes, routeSizes, numRoutes, source, target);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(N × M)

N routes × M average stops per route, each stop/bus visited once

✓ Linear Growth

Space Complexity

O(N × M)

HashMap storing stop→buses mapping plus BFS queue space

✓ Linear Space

89.2K Views

Medium Frequency

~35 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler