LeetCode 815. Bus Routes

[@sandeepradhakrishnapadhi6366]

Thankyou sir..!! Sir can you suggest some good hard problems along similar lines?

[@veilmk5]

讲的非常好 谢谢

[@deedee_358]

Really liked the explanation for the approach taken. Understood the problem and the solution quite well. Thanks a lot Sir for this wonderful video. Subscribed to your channel and would love to share the info of this channel with my other coder friends. Looking forward for more such videos.

[@happycoding1093]

thank you for your support!

[@alammahtab08]

Any idea how to get all the possible routes from A to B.

[@arupdas2210]

Thank you very much for the explanation. Here is my C++ code based on above logic. Wishing you all a very happy Diwali. class Solution { public: // We will perform BFS on the source node and continue traversing // until we reach the target node. The number of different routes we // encounter is the answer. // Time Complexity: O(mn) // Space Complexity: O(mn) int numBusesToDestination(vector& routes, int source, int target) { int m; // no. of routes int n; // no. of stops in a bus route int ans; queue q; unordered_set seen_stops; unordered_set seen_routes; unordered_map graph; ans = 0; m = routes.size(); // Time Complexity: O(mn) for(int route_id = 0; route_id < m; route_id++) { for(auto stop : routes[route_id]) { graph[stop].push_back(route_id); } } q.push(source); seen_stops.insert(source); while(!q.empty()) { // Time Complexity: O(m) int cnt = q.size(); for(int j = 0; j < cnt; j++) { // Time Complexity: O(n) int bus_stop = q.front(); q.pop(); if(bus_stop == target) { return ans; } for(int route_id : graph[bus_stop]) { if(seen_routes.find(route_id) == seen_routes.end()) { // mark route_id as visited seen_routes.insert(route_id); n = routes[route_id].size(); // visit all stops in the given route for(int i = 0; i < n; i++) { int stop = routes[route_id][i]; if(seen_stops.find(stop) == seen_stops.end()) { // mark bus stop as visited seen_stops.insert(stop); q.push(stop); } } } } } ans++; } return -1; } };