Bus Routes

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in companies
American ExpressUberMcKinsey & Company

Problem statement

This time Ninja is helping a lost passenger on a bus stop to reach his destiny with the minimum number of buses he needs to change, on the bus stop a chart is present which contains 'N' arrays. An array 'A' denotes the route that a bus will take, such that A[i] denotes the bus stop 'i'th bus will travel to.

For Example 
If the bus route is [3, 6, 7], then it will travel  in sequence 
3 > 6 > 7 > 3 > 6 > 7….

You can travel between the bus stations through buses only. You are given the source bus station and destination bus station. You need to determine the minimum number of buses you need to reach the destination. If it is not possible to reach destination return -1.

Note: 
Values of A[i] are distinct.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of the test case contains ‘N’, ‘SOURCE’, ‘TARGET’ denoting the number of buses, source station, and target station.

The next ‘N’ lines contain the stations that the bus will travel to. 

The first integer of the ith line contains the total number of bus stations ith bus will travel to. 

The next A[i][j] integers denote the bus station’s number of ith bus.
Output Format 
For each test case, return the single integer denoting the minimum number of buses to take to travel from source to destination. If it is not possible to reach destination return -1.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 400
1 <= sum(length of A[i]) <= 10^5
0 <= A[i][j], ‘SOURCE’, ‘TARGET’ <=10^6

Time Limit: 1 sec
Sample Input 1
1
2 6 7
3 1 5 6
3 5 7 8
Sample Output 1
2
Explanation:
For the first test case.
The best possible ans is to take 1st bus from 6th station.
Then from 6th station travel to 5th station using the first bus.
Then change the bus at 5th station and take the 2nd bus.
From 2nd bus travel to 7th station. Thus the answer is 2.
Sample Input 2:
1
2 7 8
3 1 2 6
3 5 6 7
Sample Output 2:
-1
Hint

Try to visit all stations of each bus, starting from the source stations.

Approaches (1)
BFS

The main idea is to do breadth-first search traversal from the source station. From the source station, we will traverse to the bus station which we can traverse using different buses.

Algorithm:-

  • Create a ‘MIN_BUSES’ array with the default value infinity. Make MIN_BUSES[SOURCE]=0(Since we don’t need any bus to travel to the source station).
  • Create an adjacency list such that BUSTATION[i] contains the list of buses that will visit the ith bus station.
  • Start bfs traversal from the source bus station. Traverse all the buses that will visit the current bus station. If the bus is already visited move to next. Else mark the bus visited and traverse all stations corresponding to the bus. If the number of buses to visit the current station  is greater than MIN_BUSES[current]+1 then replace MIN_BUSES[current1] by MIN_BUSES[current]+1.
  • After bfs traversal if the MIN_BUSES[destination] is equal to infinity then return -1(since there is no path).Else return MIN_BUSES[destination].
Time Complexity

O(N), where ‘N’ is the number of stations.

 

In the worst case, we need to travel to all bus stations. Hence time complexity is O(N).

Space Complexity

O(max(A[i][j])), where ‘max(A[i][j])’ is the maximum value for the bus stop.

 

Creating an auxiliary distance array of size ‘max(A[i][j])’.

Code Solution
(100% EXP penalty)
Bus Routes
Full screen
Console