Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Bus Routes
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given an array routes where routes[i] is the list of bus stops that the i<sup>the</sup> 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<sup>5</sup>
  • All the values of routes[i] are unique.
  • sum(routes[i].length) <= 10<sup>5</sup>
  • 0 <= routes[i][j] < 10<sup>6</sup>
  • 0 <= source, target < 10<sup>6</sup>

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

Python3
Python3

. . . .

Complexity Analysis

Time Complexity

  • Constructing the stopToBuses map requires iterating over each route and each stop within the route, which takes O(M \times K) 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 O(M \times K \times M) time, resulting in a total time complexity of O(M^2 \times K).

Space Complexity

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

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible