1129. Shortest Path with Alternating Colors | LeetCode Medium | Graphs | BFS

[@deepcodes]

class Solution { public: //red->0 and blue->1 vector shortestAlternatingPaths(int n, vector& redEdges, vector& blueEdges) { vectoradj(n); for (auto &it : redEdges) { adj[it[0]].push_back({it[1], 0}); } for (auto &it : blueEdges) { adj[it[0]].push_back({it[1], 1}); } vectorans(n, -1); vectorvisited(n, vector(2)); queueq; q.push({0, 0, -1}); //node, steps, color visited[0][0] = true; visited[0][1] = true; ans[0] = 0; while (!q.empty()) { vectorcurr = q.front(); q.pop(); int node = curr[0], steps = curr[1], prevColor = curr[2]; for (auto& [neighbour, color] : adj[node]) { if (!visited[neighbour][color] && color != prevColor) { visited[neighbour][color] = true; q.push({neighbour, 1+steps, color}); if (ans[neighbour] == -1) { ans[neighbour] = 1+steps; } } } } return ans; } };

[@vineetkumar2899]

after searching a lot of articles and videos I found this one. Awesome explanation✨

[@peter9759]

Good Explanation Bro everything connects

[@acceleratorlevel645]

great approach , i also had a similar approach by pairing up nodes and color in adj list, had difficulty in updating the distance array, your second if statement in the for loop was something i didnt think of , helped me a lot! thanks

[@deepcodes]

Thanks, you 're welcome.

[@CleverSuree]

I started to follow you from 1 of Feb. day by day your explanation style improving. Good Work .

[@deepcodes]

Thanks a lot 😊

[@sadikulhaquesadi6003]

Thanks man!!! Thanks for the effort!! After trying DFS and normal visited array I was about to give up. Then Saw this video and the idea of using BFS and visited[node][color] trick has been accepted

[@deepcodes]

Great to hear, thank you!

[@mdkashifraza2603]

Thank You for nice explanation😁

[@deepcodes]

You're welcome 😊, thanks!

[@prajitbanerjee8226]

nice bro!!

[@ITArchanaGK]

Thank you. Very much understandable👍

[@deepcodes]

Thanks, You are welcome!

[@himashisbiswas1339]

great explanation . that modified visited array thing was really smart. how did you came up with that idea ? i was solving using using a queue of node,steps,and previous color but the visited array thing was making it wrong.

[@deepcodes]

From the hint, parallel edges. Thank you!

[@abhishek__anand__]

Great Code 😉

[@deepcodes]

Thanks 😁

[@mohamedhesham6008]

Very good keep going (: thank you

[@deepcodes]

Thank you! 😃

[@girikgarg8]

How do you think of the approach to such questions? I mean how do you develop the intuition to such questions

[@deepcodes]

Usually I do by generating test cases.

[@CricketGalaxy07-18]

Thanks bhai 🙏🏻🙏🏻

[@deepcodes]

Thanks!

[@KrishnaSharma-bv5ys]

Nice.

[@deepcodes]

Thanks!

[@thedarkknight1865]

thanks undestood

[@deepcodes]

Thanks, You are welcome!