Making A Large Island | Brute Force | Better | Optimal | Dry Run | Leetcode 827 | codestorywithMIK

[@movvamanish1467]

I cracked Amazon and Uber in San Francisco. I am following your potd from 2 years. Continuing even now. I am about to finish my masters degree and join Amazon in May. Thanks for making people like us to get interest in DSA and Hope every subscriber of yours will get success in their life. You are truly underrated Gem 🙏 G.O.A.T 🐐

[@codestorywithMIK]

Amazing news. Many Many Congratulations 🎊🎊❤️❤️ Thank you for your kind words 🙏❤️😇

[@gui-codes]

bhai gajab. congrats man.

[@DevanshGupta-io7rl]

congrats

[@swarupdwivedy5733]

Please post your linkedin id link here, so that we can connect with you.

[@IndiansGotlatent-p3t]

bro great to hear this , but can you provide us the path way how u did that , also mention linkdin too

[@kareni7572]

Thought of the better brute force! Thanks for detailed intuition of all approaches.

[@gui-codes]

I did the 2nd approach on my own. here for the optimal approach. Thanks a lot MIK I also got January Badge

[@codestorywithMIK]

Make use of this : ✨ 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

[@deathtrick]

Bhai can you create a video on Find the smallest binary digit multiple of given number I know this is a gfg problem but I am not getting the explanation.

[@YashSinghal]

using memory optimally for reducing time complexity always amazes me!

[@PriyanshuSingh-rm5xg]

The way you solved and explained this problem is truly exceptional .😊 Thanks for being with us....

[@codestorywithMIK]

So nice of you🙏❤️😇

[@vivekgupta_3085]

Next Level Explaination , i would have skipped many question but your explaination is far better than any paid courses !!

[@codestorywithMIK]

🙏❤️ Thanks a lot for the appreciation!

[@crazygamerrohan9899]

Finally a short movie on island

[@codestorywithMIK]

❤️❤️🙏🙏

[@amitguptapc]

God level explanation

[@rickdutta942]

Solved using DSU on my own thank you Mik for you videos.💗 I never thought i can solve 'Hard' problem on my own.

[@codestorywithMIK]

That's amazing! 🎉🎉

[@rickdutta942]

​@ （づ￣3￣）づ╭❤

[@venkatarohitpotnuru38]

Super,loved the solution

[@spdh6325]

You are my love man!! Bhai you are my brother from another mother. I am working in a small service based company. I always put myself ahead of my barrier. I have improved in DSA But Your motivation always cheers up. Thank you Mik for your wonderful contribution. That Line : "Agar tum saath ho......" [agar tum saath na hote to aaj leetcode me koi account bhi nahi raheta aur DSA still tough topic of syllabus rahe jata ] Bhai bandhu mitro ho mere. I always listen your advice as a student of yours. ❤❤

[@codestorywithMIK]

Thank you so much for your kind words! It means a lot to me. 🙏❤️

[@spdh6325]

@@codestorywithMIK I m enjoying your shorts, so keep posting it. regularly you are posting your dsa videos, one day take time and made a parody video of DSA struggling make it sarcastic way. I and we will definitely love this. are padhai ke saathe thoda maza bhi chahiye

[@VaishnavI-me8bz]

thank u MIK sir.. u r the reason 4 our consistency , phle streak toot jati thi...soln na soch paane se Ab yh hota h : TRY KRTE H , NA HUA TO MIK SIR TO HI ❣.. Today after 2-3 hours same approach as ur OPTIMAL one, but code different h thoda ..T.C thodi jayada aayi h ....but phli bar hard ques khud bnaya mene🥹

[@codestorywithMIK]

😇❤️🙏

[@FanIQQuiz]

Goat for a reason

[@thefinancialdiet4458]

Thanks for the video sir❤❤❤

[@imPriyansh77]

great solution and intuition!!! Thanks bhaiya

[@ManishKumar-dy5be]

Bhaiya , aap bhut achha padhte ho aur aapse bhut kuchh sikha hai , mai aur mere dost lagbhag majority of dsa problem solve kr lete hai lekin time complexity nikalne me dikkat aati hai , space v nikal leta hu , koi trick ho ya iske critical example me video banaiye please , ye problem lagbhag sabko dekha hai Maine please, ya mujhe bta dijiye kya kru

[@codestorywithMIK]

Hi Manish, There are some tricks for this like making use of master theorem etc however I personally feel that is not required for interviews unless someone is giving gate exams. This is what I do : 1) I see the code and point out the loops and function calls - see if you can easily find their time complexity 2) Sometimes the easiest way is to see how many times you have to visit elements of a graph or 2d array or array or queue or dfs etc , depending on how many times each element is visited we can easily find their time complexity. For example: in today’s POTD, when we hit dfs, we mark cells visited and never visit a visited cell ever again. This says that we only visit m*n cells once and hence time is m*n These are small observations that helps to break a bigger code and find its time complexity

[@codestorywithMIK]

I will try to make a video for it

[@pawankumar-ic9ec]

You are the Goat Mik, lots of love ❤️

[@codestorywithMIK]

Your kind words mean a lot to me ❤️❤️🙏🙏

[@aizad786iqbal]

Thanks for making this so easy, if possible please make the video on DSU today with java code on this, Aajka question toh easy hoga since 1st feb hai aaj

[@Nitish-r4q]

Congralutions 🎉 sir , Now you are famous in NIT Patna everyone follow your lecture

[@codestorywithMIK]

🙏❤️ thank you for the appreciation!

[@HarishKumar-jm5bk]

Bhai solution kafi acha ha apka no doubt but isko dsu se bhi kr skte ha can u discuss that approach 😊

[@indianengineer5802]

I did problem with union find. Along with parent and rank array I also had one childCount where i am tracking the childCount of each parent. Now i just traversed over all the cells and went to nbrs and added childCount of nbrs having diff parent

[@codestorywithMIK]

Wonderful 🔥

[@fabhacker]

same approach i did as well

[@aryansinha1818]

I always try to find your second channel link but couldn't, please drop the link.

[@codestorywithMIK]

youtube.com/@weekendwithmik?si=mqkq_EgcFslyqHWL Appreciate your support 😇🙏❤️

[@aryansinha1818]

@codestorywithMIK Subscribed 🙌🎊

[@AS-gf3ci]

Using DSU : class DisjointSet { public: vector parent; vector rank, size; DisjointSet(int n) { parent.resize(n+1); //For incorporating 1-based indexing graphs as well rank.resize((n+1), 0); size.resize((n+1), 1); for(int i = 0; i rank[v_parent]) //Making v_parent > u_parent for minimal code swap(u_parent, v_parent); parent[u_parent] = v_parent; //Handles all 3 cases if(rank[u_parent] == rank[v_parent]) rank[v_parent]++; } void unionBySize(int u, int v) { int u_parent = findParent(u); int v_parent = findParent(v); if(u_parent == v_parent) return; if(size[u_parent] > size[v_parent]) { //Making u_parent as the parent of v_parent parent[v_parent] = u_parent; size[u_parent] += size[v_parent]; } else { parent[u_parent] = v_parent; size[v_parent] += size[u_parent]; } } }; class Solution { public: int largestIsland(vector& grid) { int n = grid.size(); int len = (n * n); DisjointSet ds(len); int dx[] = {0, 0, -1, 1}; //LRUD int dy[] = {-1, 1, 0, 0}; //Step 1 : Connect components & store component size in the size array of ds for(int i=0; i

[@thefinalfit]

3rd approach 🔥

[@shreyxnsh.14]

Please tell the DSU approach also, maybe upload another video if you feel this one went too long

[@zaffarzeshan1308]

java code class Solution { public int largestIsland(int[][] grid) { int m = grid.length; HashMap map= new HashMap(); int max=Integer.MIN_VALUE; int id=2; //n == grid[i].length for(int i=0;i1 && vis.add(grid[i][j-1])){ int x=map.get(grid[i][j-1]); sum+=x; } max=Math.max(max,sum); } } } return (max==Integer.MIN_VALUE)?m*m:max; } int dfs(int id, int i, int j, int m,int [][]grid){int count=1; if (i < 0 || j < 0 || i >= m || j >= m || grid[i][j] != 1) return 0; grid[i][j]=id; count += dfs(id,i+1,j,m,grid); count += dfs(id,i-1,j,m,grid); count += dfs(id,i,j+1,m,grid); count += dfs(id,i,j-1,m,grid); return count; } boolean checkvalid(int i,int j, int m){ return i >= 0 && j >= 0 && i < m && j < m; } }

[@DailyUSA-kh3jj]

Mik we are calculating area efficiently in body two then y are you updating maxarea in body 1 plz tell me.

[@Himanshukumar-ru2vt]

Bhaiya aap java language me bhi code upload kr diya kro please ya toh aap java me bhi code kriye jisse java students ko bhi help ho jaye please

[@Himanshukumar-ru2vt]

Bhaiya toh kabse aap upload karenge yej bta dijiye kyuki bahut jarurat hota hai aap bht aache se smjhate hai lakein c++ me code hota hai toh uski wajah se smjh nhi ata java me change kaise kare

[@PunitTiwari-t1c]

Could you please create a video ok K empty slots(683). It has been asked in google. Please

[@prasadagalave9762]

I was able to get brut force soln

[@kumarbishwajeet5269]

Isn't this unique id approach equivalent to DSU using union by size. WE can get the parents node and its size

[@codestorywithMIK]

Definitely. Do check out Approach 4 in the GitHub link in the description using DSU ❤️🙏

[@ujjwal8514]

Can you explain a little more quickly? btw Nice Explanation ❣

[@AFFFFGAMER]

1st comment like from mandai kala 😁

[@gui-codes]

Mandai kala kaha hai bhai ?

[@AFFFFGAMER]

@@gui-codes space me 🌌 🚀

[@ComputerCentre-rn2yy]

10:00

[@thefinancialdiet4458]

Sir updates sheet and guidance how to do that?❤❤❤😅😅

[@hemant_kumar_071]

class DSU{ public: vector parent,size; DSU(int n){ parent.resize(n); size.resize(n,1); for(int i=0;i size[v_parent]){ parent[v_parent]=u_parent; size[u_parent]+=size[v_parent]; } else if(size[v_parent] > size[u_parent]){ parent[u_parent]=v_parent; size[v_parent]+=size[u_parent]; } else{ parent[v_parent]=u_parent; size[u_parent]+=size[v_parent]; } } }; class Solution { public: int largestIsland(vector& grid) { int n = grid.size(); int totalCells = n*n; DSU dsu(totalCells); int drow[] = {1,0,-1,0}; int dcol[] = {0,1,0,-1}; for(int row=0;row

[@kulvardhansinghrathore7201]

BFS: int BFS(vector& grid, int i, int j, int& islandId, int& m, int& n){ queue que; que.push({i, j}); grid[i][j] = islandId; int count = 1; while(!que.empty()){ auto [i_, j_] = que.front(); que.pop(); for(vector& dir : dirs){ int x = i_ + dir[0]; int y = j_ + dir[1]; if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1){ que.push({x, y}); grid[x][y] = islandId; count++; } } } return count; }

[@unknown__899]

my dsu solution ,class Solution { public: int r; int c; int find(int idx, vector& prt) { if (prt[idx] == idx) return idx; return prt[idx] = find(prt[idx], prt); } void unionn(int i, int j, vector& size, vector& prt) { int rootI = find(i, prt); int rootJ = find(j, prt); if (rootI == rootJ) return; // Already in the same set if (size[rootI] >= size[rootJ]) { prt[rootJ] = rootI; size[rootI] += size[rootJ]; // Update size of new root } else { prt[rootI] = rootJ; size[rootJ] += size[rootI]; // Update size of new root } } void dfs(int i, int j, vector& grid, vector& size, vector& prt) { int idx1 = i * c + j; grid[i][j] = 0; if (i - 1 >= 0 && grid[i - 1][j] != 0) { int idx2 = (i - 1) * c + j; unionn(idx1, idx2, size, prt); dfs(i - 1, j, grid, size, prt); } if (i + 1 < r && grid[i + 1][j] != 0) { int idx2 = (i + 1) * c + j; unionn(idx1, idx2, size, prt); dfs(i + 1, j, grid, size, prt); } if (j - 1 >= 0 && grid[i][j - 1] != 0) { int idx2 = i * c + (j - 1); unionn(idx1, idx2, size, prt); dfs(i, j - 1, grid, size, prt); } if (j + 1 < c && grid[i][j + 1] != 0) { int idx2 = i * c + (j + 1); unionn(idx1, idx2, size, prt); dfs(i, j + 1, grid, size, prt); } } int largestIsland(vector& grid) { r = grid.size(); c = grid.size(); unordered_set st; unordered_set st2; vector cpgrid(r, vector(c, -1)); vector size(r * c, 0); vector prt(r * c, 0); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { int idx = i * c + j; size[idx] = grid[i][j]; } } for (int i = 0; i < r * c; i++) { prt[i] = i; } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cpgrid[i][j] = grid[i][j]; } } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (grid[i][j] == 1) { dfs(i, j, grid, size, prt); } } } int ans = INT_MIN; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (cpgrid[i][j] == 0) { int x =1; if (i - 1 >= 0) { int idx2 = (i - 1) * c + j; st.insert(find(idx2,prt)); } if (i + 1 < r) { int idx2 = (i + 1) * c + j; st.insert(find(idx2,prt)); } if (j - 1 >= 0) { int idx2 = i * c + (j-1); st.insert(find(idx2,prt)); } if (j + 1 < c) { int idx2 = i * c + (j+1); st.insert(find(idx2,prt)); } for(auto val:st){ x+=size[val]; } ans=max(ans,x); st=st2; } } } if(ans==INT_MIN){ return r*c; } return ans; } };

[@vishwashsoni610]

sir try kiya tha lakin TLE chala gaya...🥲 class Solution { public: vector dir = {{0,1},{0,-1},{1,0},{-1,0}}; int BFS(int i,int j,vector& grid,int n){ vectorvisited(n,vector(n,false)); queueq; q.push({i,j}); visited[i][j] = true; int count = 1; while(!q.empty()){ auto [u,v] = q.front(); q.pop(); for(auto x : dir){ int i_ = x[0]+u; int j_ = x[1]+v; if(i_=0 && j_=0 && grid[i_][j_]==1 && visited[i_][j_] == false){ visited[i_][j_] = true; q.push({i_,j_}); count++; } } } return count; } int largestIsland(vector& grid) { int n = grid.size(); int largestIsland = 0; for(int i=0;i

[@aakashdeep_2310]

Anyone From LPU

[@varunpalsingh3822]

I got stuck at 71th test case due to TLE, now I'm here, I always try to solve on my own first, if I stuck then only see your video, your graph concept && question playlist is best ✅

[@codestorywithMIK]

Very well ❤️ Always try from your own first. Great job

[@dayashankarlakhotia4943]

i submitted solutions without set and map. public int largestIsland(int[][]grid){ int n=grid.length; int[]size=new int[2+n*n]; int maxSize=0,id=2; for(int i=0;i

[@Mahidhar-w8p]

My python solution ``````````````````````````` class Solution: def largestIsland(self, grid: List[List[int]]) -> int: def dfs(i,j,island_idx): if i < 0 or i == N or j < 0 or j == N or grid[i][j] != 1: return 0 grid[i][j] = island_idx return 1 + dfs(i+1,j,island_idx) + dfs(i-1,j,island_idx) + dfs(i,j+1,island_idx) + dfs(i,j-1,island_idx) N = len(grid) res = 0 islands = {} island_idx = 2 for i in range(N): for j in range(N): if grid[i][j] == 1: island_size = dfs(i,j,island_idx) islands[island_idx] = island_size res = max(res,island_size) island_idx += 1 for i in range(N): for j in range(N): if grid[i][j] == 0: unique_islands = set() land = 1 for i_,j_ in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]: if i_ >= 0 and i_ < N and j_ >= 0 and j_ < N and grid[i_][j_] != 0: if grid[i_][j_] not in unique_islands: land += islands[grid[i_][j_]] unique_islands.add(grid[i_][j_]) res = max(res, land) return res ``````````````````````````