Redundant Connection | DSU | DFS | BFS | Leetcode 684 | codestorywithMIK
370Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
Hi Everyone, this is the 66th video of our Playlist "Graphs : Popular Interview Problems".
Now we will be solving a good practice problem on Graph for DFS, BFS and DSU - Redundant Connection | DSU | DFS | BFS | Leetcode 684 | codestorywithMIK
We will discuss a detailed explanation for DSU specially as it will teach us a lot of things.
Disjoint Set Union | DSU - • Disjoint Set Union | DSU | Graph Conc...
DSU by Rank and Path Compression - • Disjoint Set Union By Rank and Path C...
DSU by Size - • Disjoint Set Union By SIZE and Path C...
Problem Name : Redundant Connection | DSU | DFS | BFS | Leetcode 684 | codestorywithMIK
Company Tags : GOOGLE
My solutions on Github(C++ & JAVA) - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Redundant Connection.cpp
Leetcode Link : https://leetcode.com/problems/redundant-connection
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Segment Tree Concepts Playlist : • Segment Tree | Introduction | Basics ...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
Trie Playlist - • Word Search II (Google, Amazon, Meta,...
Difference Array Technique: Concepts & Qns : • Introduction | What | How | Differenc...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Video Summary :
Intuition and Thought Process
1️ ⃣ Approach-1 (DFS)
Treat the graph as an undirected structure and build it edge by edge.
Before adding an edge, check if both nodes are already connected using DFS.
If they are, adding this edge creates a cycle, making it redundant.
2️ ⃣ Approach-2 (BFS)
Instead of DFS, use BFS to check if two nodes are already connected before adding an edge.
If a path already exists between them, adding the edge forms a cycle, making it redundant.
3️ ⃣ Approach-3 (Disjoint Set Union - DSU)
Use the Union-Find data structure to track connected components efficiently.
If two nodes of an edge belong to the same component, the edge is redundant.
Path compression and union by rank help optimize the process.
✨ Timelines✨
00:00 - Introduction
0:23 - Motivation
1:22 - Problem Explanation
05:35 - One Fact
07:27 - Thought Process DFS/BFS
15:16 - Coding DFS
19:30 - DSU Intuition
25:52 - Coding DSU
#MIK #mik #Mik #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #codestorywithmik #codestorywithmick #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik