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 🐐
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
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.
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🥹
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 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
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
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
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
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
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
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; } }
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
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; }
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 ✅
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
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 ``````````````````````````
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 🐐
Amazing news. Many Many Congratulations 🎊🎊❤️❤️
Thank you for your kind words 🙏❤️😇
bhai gajab. congrats man.
congrats
Please post your linkedin id link here, so that we can connect with you.
bro great to hear this , but can you provide us the path way how u did that , also mention linkdin too
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
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.
I did the 2nd approach on my own.
here for the optimal approach. Thanks a lot MIK
I also got January Badge
Thought of the better brute force! Thanks for detailed intuition of all approaches.
using memory optimally for reducing time complexity always amazes me!
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🥹
😇❤️🙏
Finally a short movie on island
❤️❤️🙏🙏
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. ❤❤
Thank you so much for your kind words! It means a lot to me. 🙏❤️
@@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
Solved using DSU on my own thank you Mik for you videos.💗
I never thought i can solve 'Hard' problem on my own.
That's amazing! 🎉🎉
@ （づ￣3￣）づ╭❤
The way you solved and explained this problem is truly exceptional .😊
Thanks for being with us....
So nice of you🙏❤️😇
Next Level Explaination , i would have skipped many question but your explaination is far better than any paid courses !!
🙏❤️ Thanks a lot for the appreciation!
Great explanation
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
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
I will try to make a video for it
Goat for a reason
Congralutions 🎉 sir , Now you are famous in NIT Patna everyone follow your lecture
🙏❤️ thank you for the appreciation!
Thanks for the video
God level explanation
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
Wonderful 🔥
same approach i did as well
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
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
great solution and intuition!!! Thanks bhaiya
Super,loved the solution
You are the Goat Mik, lots of love ❤️
Your kind words mean a lot to me ❤️❤️🙏🙏
Thanks for the video sir❤❤❤
Bhai solution kafi acha ha apka no doubt but isko dsu se bhi kr skte ha can u discuss that approach 😊
I always try to find your second channel link but couldn't, please drop the link.
youtube.com/@weekendwithmik?si=mqkq_EgcFslyqHWL
Appreciate your support 😇🙏❤️
@codestorywithMIK Subscribed 🙌🎊
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;
}
}
3rd approach 🔥
Can you explain a little more quickly? btw Nice Explanation ❣
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
Mik we are calculating area efficiently in body two then y are you updating maxarea in body 1 plz tell me.
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
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
10:00
Could you please create a video ok K empty slots(683). It has been asked in google. Please
Please tell the DSU approach also, maybe upload another video if you feel this one went too long
1st comment like from mandai kala 😁
Mandai kala kaha hai bhai ?
@@gui-codes space me 🌌 🚀
Isn't this unique id approach equivalent to DSU using union by size. WE can get the parents node and its size
Definitely. Do check out Approach 4 in the GitHub link in the description using DSU ❤️🙏
I was able to get brut force soln
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;
}
Sir updates sheet and guidance how to do that?❤❤❤😅😅
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;
}
};
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
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 ✅
Very well ❤️
Always try from your own first. Great job
Anyone From LPU
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
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
``````````````````````````