Most Stones Removed with Same Row or Column | Using DSU | DRY RUN | Leetcode 947 | codestorywithMIK
241Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 55th Video of our Playlist "Graphs : Popular Interview Problems" by codestorywithMIK
Using DFS - • Most Stones Removed with Same Row or ...
DSU-1 - • Disjoint Set Union | DSU | Graph Conc...
DSU-2 - • Disjoint Set Union By Rank and Path C...
In this video we will try to solve a very good Graph Problem : Most Stones Removed with Same Row or Column | Using DSU | FULL DRY RUN | Leetcode 947 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Most Stones Removed with Same Row or Column | Using DSU | FULL DRY RUN | Leetcode 947 | codestorywithMIK
Company Tags : GOOGLE
My solutions on Github(C++ & JAVA) - https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/most-st...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
This approach uses the Union-Find (Disjoint Set Union, DSU) data structure to solve the problem of removing the maximum number of stones from a 2D grid while keeping at least one stone in each connected component.
Key Concepts:
Union-Find Structure:
The parent array keeps track of the representative (root) of each set.
The rank array helps optimize the union operation by attaching the smaller tree under the root of the larger tree (union by rank).
The find function applies path compression, ensuring that each node points directly to its root, reducing the time complexity for future queries.
Initialization:
The parent and rank arrays are initialized for each stone. Initially, every stone is its own parent, representing a separate set.
Union Operation:
Stones are considered connected if they share the same row or column. For each pair of stones that satisfy this condition, the Union operation merges their sets.
Counting Connected Components:
After processing all stones, the algorithm counts the number of unique connected components by checking which elements are their own parents.
Result:
The maximum number of stones that can be removed is calculated as n - groups, where n is the total number of stones, and groups is the number of connected components. This is because, in each component, only one stone needs to be left, and the rest can be removed.
This approach efficiently finds and merges connected components using Union-Find, ensuring that the algorithm runs in nearly linear time complexity.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024