hard Bus Routes

Problem Statement

You are given an array routes where routes[i] is the list of bus stops that the i^the bus travels in a cyclic manner. For example, if routes[0] = [2, 3, 7], it means that bus 0 travels through the stops 2 -> 3 -> 7 -> 2 -> 3 -> 7 ... and then repeats this sequence indefinitely.

You start at a bus stop called source and wish to travel to a bus stop called target using the bus routes. You can switch buses at any bus stop that is common to the routes of two buses.

Return the minimum number of buses you need to take to travel from source to target. If it is not possible to reach the target, return -1.

Examples

Example 1

• Input: routes = [[2, 3, 4], [5, 6, 7, 8], [4, 5, 9, 10], [10, 12]], source = 3, target = 12
• Expected Output: 3
• Justification: Start at stop 3, take bus 0 to stop 4, switch to bus 2 to reach stop 10, and then take bus 3 to reach to 12. You need 3 buses.

Example 2

• Input: routes = [[1, 2, 3, 4, 5], [5, 6, 7, 8], [8, 9, 10, 11]], source = 1, target = 11
• Expected Output: 3
• Justification: Start at stop 1, take bus 0 to stop 5, switch to bus 1 to reach stop 8, then switch to bus 2 to reach stop 11. You need 3 buses.

Example 3

• Input: routes = [[1, 2, 5], [3, 6, 7], [7, 9, 10]], source = 2, target = 10
• Expected Output: -1
• Justification: It is not possible to reach from bus stop 2 to 10.

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⁶

Solution

To solve this problem, we can use the Breadth-First Search (BFS) algorithm. The problem requires us to find the shortest path in terms of bus transfers from the source to the target stop. BFS is suitable because it explores all possible routes level by level, ensuring that we find the shortest path first.

We'll start from the source stop and explore all buses that can be taken from there. For each bus, we'll check all stops it visits and mark them as visited to avoid reprocessing. We'll then repeat this process for each newly reached stop until we reach the target stop or exhaust all possibilities. This ensures that we find the minimum number of bus transfers needed to reach the target.

Step-by-step Algorithm

1. Initialization:

   • Create a map stopToBuses where the key is a bus stop and the value is a list of buses that visit this stop.
   • Initialize an empty queue for BFS, queue, which will store pairs of (current_stop, buses_taken).
   • Initialize a set visitedStops to keep track of bus stops that have been visited.
   • Initialize a set usedBuses to keep track of buses that have been used.

2. Building the stopToBuses Map:

   • For each bus route in routes, and for each stop in that route, add the bus index to the list of buses in the stopToBuses map for that stop.

3. Start BFS:

   • Enqueue the source stop with 0 buses taken (queue.offer(new int[]{source, 0})).
   • Mark the source stop as visited (visitedStops.add(source)).

4. Processing the Queue:

   • While the queue is not empty:
     • Dequeue the front element from the queue to get the current stop and the number of buses taken so far.
     • For each bus that visits the current stop:
       • If the bus has already been used, skip it.
       • Mark the bus as used (usedBuses.add(bus)).
       • For each stop that this bus visits:
         • If this stop is the target, return the number of buses taken plus one.
         • If this stop has not been visited yet, mark it as visited and enqueue it with the number of buses taken plus one.

5. If Target Not Reached:

   • If the queue is empty and the target has not been reached, return -1.

Algorithm Walkthrough

Input:

• routes: [[2, 3, 4], [5, 6, 7, 8], [4, 5, 9, 10], [10, 12]]
• source: 3
• target: 12

1. Initialization:

   • stopToBuses map: {} initially.
   • queue: []
   • visitedStops: {}
   • usedBuses: {}

2. Building the stopToBuses Map:

   • Final stopToBuses map: {2: [0], 3: [0], 4: [0, 2], 5: [1, 2], 6: [1], 7: [1], 8: [1], 9: [2], 10: [2, 3], 12: [3]}

3. Start BFS:

   • Enqueue (3, 0): queue = [(3, 0)]
   • Mark 3 as visited: visitedStops = {3}

4. Processing the Queue:

   • Dequeue (3, 0): current_stop = 3, buses_taken = 0
     • Buses visiting stop 3: [0]
       • Bus 0:
         • Stops visited by bus 0: [2, 3, 4]
         • Stop 2:
           • Not the target, mark visited and enqueue: queue = [(2, 1)], visitedStops = {2, 3}
         • Stop 3:
           • Already visited, skip.
         • Stop 4:
           • Not the target, mark visited and enqueue: queue = [(2, 1), (4, 1)], visitedStops = {2, 3, 4}
   • Dequeue (2, 1): current_stop = 2, buses_taken = 1
     • Buses visiting stop 2: [0] (already used, skip)
   • Dequeue (4, 1): current_stop = 4, buses_taken = 1
     • Buses visiting stop 4: [0, 2]
       • Bus 0:
         • Already used, skip.
       • Bus 2:
         • Stops visited by bus 2: [4, 5, 9, 10]
         • Stop 4:
           • Already visited, skip.
         • Stop 5:
           • Not the target, mark visited and enqueue: queue = [(5, 2)], visitedStops = {2, 3, 4, 5}
         • Stop 9:
           • Not the target, mark visited and enqueue: queue = [(5, 2), (9, 2)], visitedStops = {2, 3, 4, 5, 9}
         • Stop 10:
           • Not the target, mark visited and enqueue: queue = [(5, 2), (9, 2), (10, 2)], visitedStops = {2, 3, 4, 5, 9, 10}
   • Dequeue (5, 2): current_stop = 5, buses_taken = 2
     • Buses visiting stop 5: [1, 2]
       • Bus 1:
         • Stops visited by bus 1: [5, 6, 7, 8]
         • Stop 5:
           • Already visited, skip.
         • Stop 6:
           • Not the target, mark visited and enqueue: queue = [(9, 2), (10, 2), (6, 3)], visitedStops = {2, 3, 4, 5, 6, 9, 10}
         • Stop 7:
           • Not the target, mark visited and enqueue: queue = [(9, 2), (10, 2), (6, 3), (7, 3)], visitedStops = {2, 3, 4, 5, 6, 7, 9, 10}
         • Stop 8:
           • Not the target, mark visited and enqueue: queue = [(9, 2), (10, 2), (6, 3), (7, 3), (8, 3)], visitedStops = {2, 3, 4, 5, 6, 7, 8, 9, 10}
       • Bus 2:
         • Already used, skip.
   • Dequeue (9, 2): current_stop = 9, buses_taken = 2
     • Buses visiting stop 9: [2] (already used, skip)
   • Dequeue (10, 2): current_stop = 10, buses_taken = 2
     • Buses visiting stop 10: [2, 3]
       • Bus 2:
         • Already used, skip.
       • Bus 3:
         • Stops visited by bus 3: [10, 12]
         • Stop 10:
           • Already visited, skip.
         • Stop 12:
           • Target reached, return buses_taken + 1 = 3.

5. Result:

   • The minimum number of buses needed is 3.

Code

import java.util.*;

public class Solution {

  // Method to find the minimum number of buses required to travel from source to target
  public int numBusesToDestination(int[][] routes, int source, int target) {
    if (source == target) return 0; // If source and target are the same, no bus is needed

    // Map bus stops to buses that visit them
    Map<Integer, List<Integer>> stopToBuses = new HashMap<>();
    for (int i = 0; i < routes.length; i++) {
      for (int stop : routes[i]) {
        stopToBuses.computeIfAbsent(stop, k -> new ArrayList<>()).add(i);
        // Create a mapping from each stop to the list of buses that visit that stop
      }
    }

    // BFS setup
    Queue<int[]> queue = new LinkedList<>();
    Set<Integer> visitedStops = new HashSet<>();
    Set<Integer> usedBuses = new HashSet<>();

    queue.offer(new int[] { source, 0 }); // Start BFS with the source stop and 0 buses taken
    visitedStops.add(source); // Mark the source stop as visited

    while (!queue.isEmpty()) {
      int[] current = queue.poll(); // Dequeue the current stop and buses taken
      int stop = current[0];
      int buses = current[1];

      for (int bus : stopToBuses.get(stop)) {
        if (usedBuses.contains(bus)) continue; // Skip buses that have already been used
        usedBuses.add(bus); // Mark the current bus as used

        for (int nextStop : routes[bus]) {
          if (nextStop == target) return buses + 1; // Found the target stop
          if (visitedStops.add(nextStop)) {
            queue.offer(new int[] { nextStop, buses + 1 }); // Enqueue the next stop with one more bus taken
          }
        }
      }
    }

    return -1; // If target is not reachable, return -1
  }

  // Main method to test the solution with provided examples
  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    int[][] routesA = {
      { 2, 3, 4 },
      { 5, 6, 7, 8 },
      { 4, 5, 9, 10 },
      { 10, 12 },
    };
    System.out.println(solution.numBusesToDestination(routesA, 3, 12)); // Output: 3

    // Example 2
    int[][] routesB = { { 1, 2, 3, 4, 5 }, { 5, 6, 7, 8 }, { 8, 9, 10, 11 } };
    System.out.println(solution.numBusesToDestination(routesB, 1, 11)); // Output: 3

    // Example 3
    int[][] routesC = { { 1, 2, 5 }, { 3, 6, 7 }, { 7, 9, 10 } };
    System.out.println(solution.numBusesToDestination(routesC, 2, 10)); // Output: -1
  }
}

Complexity Analysis

Time Complexity

• Constructing the stopToBuses map requires iterating over each route and each stop within the route, which takes time, where (M) is the number of routes and (K) is the average number of stops per route.
• During the BFS, each bus route and each stop will be processed. For each route in the queue, we iterate over its stops, and for each stop, we iterate over the connected routes in the map stopToBuses. This takes time, resulting in a total time complexity of .

Space Complexity

• The stopToBuses map requires space to store all bus stops and their corresponding routes.
• The BFS queue can store up to elements in the worst case.
• The visitedStops and usedBuses sets will store up to elements.
• Thus, the total space complexity is .