Making A Large Island | Brute Force | Better | Optimal | Dry Run | Leetcode 827 | codestorywithMIK
397Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
Hi Everyone, this is the 68th video of our Playlist "Graphs : Popular Interview Problems".
Now we will be solving a good practice problem on Graph for DFS, BFS - Making A Large Island | Brute Force | Better | Optimal | Detailed Dry Run | Leetcode 827 | codestorywithMIK
We will discuss a detailed explanation. From brute force to a better and then to an optimal solution.
Problem Name : Making A Large Island | Brute Force | Better | Optimal | Detailed Dry Run | Leetcode 827 | codestorywithMIK
Company Tags : Google, Uber
My solutions on Github(C++ & JAVA) - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/BFS_DFS/Making A Large Island.cpp
Leetcode Link : https://leetcode.com/problems/making-a-large-island/
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 :
1️ ⃣ Approach-1 (Brute Force DFS)
The idea is to try converting each 0 into 1 and then compute the largest island.
Iterate over every cell, change 0 to 1, and then use DFS to find the size of the largest island.
Since DFS is performed for every modification, the time complexity is very high (O(n^4)).
This approach is inefficient due to repeated DFS calls for each modification.
2️ ⃣ Approach-2 (Better Brute Force DFS)
Instead of running DFS multiple times, preprocess the initial island sizes.
First, find the size of all connected 1 components and store their values.
Then, for each 0, change it to 1 and compute the largest connected component using a single DFS.
This avoids unnecessary recomputation and slightly optimizes performance but still runs in O(n^4).
3️ ⃣ Approach-3 (Optimal DFS with Component Marking)
Rather than recomputing island sizes repeatedly, assign unique IDs to each island and store their sizes in a hashmap.
First, use DFS to mark each island with a unique ID and store its size.
Then, for every 0, check its neighboring islands (by ID) and sum their sizes to determine the largest possible island.
This reduces redundant DFS calls and brings down the time complexity to O(m*n), making it optimal.
✨ Timelines ✨
00:00 - Introduction
00:19 - Motivation
01:02 - Problem Explanation
03:36 - Super Brute Force
16:24 - Coding Super Brute Force
25:18 - Better Brute Force
29:31 - Coding Better Brute Force
32:15 - Optimal Approach
53:25 - Coding Optimal Approach
#MIK #mik #Mik #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #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 #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