MIK you are a legend have a small request please start solving contest problems no one is doing that properly. Anyone else feel the same like this I will try to post this comment everyday so that MIK listens to our request.
Everyone can explain easy concepts, but the true caliber of a teacher can be understood when he teaches complex topics like these. Hats off! Frankly, I was confused when I saw the example test case diagram and hit a mental roadblock.
Your explanations are truly outstanding! You’ve made everything so easy to understand, and not only that, your help has been invaluable. May God bless you. You are a true nationalist, supporting all sections of society without expecting anything in return. You are an inspiration to the younger generation. I believe that your UA-cam channel will become extremely popular, and I pray for your success. Thank you so much a true Indian, a true nationalist, and a real hero for the youth!
32:48 is what makes you different from others. There is a big difference between feeding concepts and teaching concepts. I watched neetcode and some others videos in the morning and decided to wait for you. my doubts, and my all answers are always answered in your videos.
Bhaiya truly speaking from my heart, if DSA teaching is an art, You are the artist, Every time I watch your videos I got amazed by the clarity with which you explain. This world definitely needs more and more artist like you.❤❤ Take a bow man!🙌🙌
Bro you are the GOAT. Any plans on recording a LLD playlist please MIK. We as freshers want to learn LLD and I can't find any trusted resources for it.
Will you know MIK you are giving such awesome content for not even a single penny of charge, Thanks for the explaining the questions in this way, really market is full of earning money oriented but you are providing better than those all. Thanks
@@bikram3249 bhai sir ke pass itna time nhi hota,... unki respect karo..... leetcode bahut hai kyokni vo comman hai...nhi to phir koi tisra aayega.. or us platform ka name leke bolega....leetcode ki problem acchi hoti hai in contest so sir vo hi karde to bhaut hai
was a good question tried to solve it using monotonic stack approach by figuring out minimum max height from all 4 directions and then subtracting the current height and ignoring boundary values and it worked for 17 cases but was not correct approach after all. Thanks for the video
Hi Mik bhai, I dont know if everyone needs to hear this or not but the 1st approach that came to my mind is to apply trapping rain water 1 column wise and then from top to bottom. Even after trying for a long long time, I failed to submit it, bcz i was getting wrong answer continuously and unable to understand why. Its almost the same approach right. Idk if i was thinking like that but ultimately bcz of this failed try, i got to understand why this approach will not work in trapping rain water 2 and i think thats my greatest victory today, even bigger than the actual submission. Failed approach ne maza dila diya.😀
Sir, thanks for this awesome lecture, there is a humble request from my side , if possible make a video on sliding window median , leetcode-480, again thank you so much for making DSA super easy.
for whom who are getting confuse that whet if any neighbouring cell is lower than the current cell ....then please observe that we already starting from the minimum from boundary cells so if you observe then the algorithm will automatically manage this situation
tomorrows motivation : opportunities hit the door of the person who word hard and i will work very very hard You are just one decision away from a totally different life
Bhai can u make neetcode 150 solutions in a separate playlist? ik most of em r already done by u but some of em are left out also neetcode explains in python but most of us need in c++ and there is no one better than u in c++ explanation. So kindly make a playlist for the solutions of neetcode150
class Solution { public: int FindEdges(vector& heightMap, int i, int j, int n, int m) { int current = heightMap[i][j]; int top = 0, bottom = 0, left = 0, right = 0; for (int t = i - 1; t >= 0; t--) { top = max(top, heightMap[t][j]); } \ for (int t = i + 1; t < n; t++) { bottom = max(bottom, heightMap[t][j]); }
for (int t = j - 1; t >= 0; t--) { left = max(left, heightMap[i][t]); }
for (int t = j + 1; t < m; t++) { right = max(right, heightMap[i][t]); }
return min({left, right, top, bottom}); } int trapRainWater(vector& heightMap) { int n = heightMap.size(); int m = heightMap[0].size(); int units = 0;
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int mini = FindEdges(heightMap, i, j, n, m); if (mini > heightMap[i][j]) { units += (mini - heightMap[i][j]); } } } return units; } }; I tried solving this question by this logic but it failed in some test case, can anyone tell me what's wrong?
MIK sir I thought of applying traping water of 1D , 1st row wise then col wise and took the min of both .. pleased tell why this logic is wrong🧠.. class Solution { vector trap(vector &arr) { int n = arr.size(); vector prefix(n), suffix(n), waterTrapped(n, 0); // Build prefix array prefix[0] = arr[0]; for (int i = 1; i < n; i++) { prefix[i] = max(prefix[i - 1], arr[i]); } // Build suffix array suffix[n - 1] = arr[n - 1]; for (int i = n - 2; i >= 0; i--) { suffix[i] = max(suffix[i + 1], arr[i]); } // Calculate trapped water for each index for (int i = 0; i < n; i++) { waterTrapped[i] = min(prefix[i], suffix[i]) - arr[i]; } return waterTrapped; } public: int trapRainWater(vector &heightMap) { int m = heightMap.size(); int n = heightMap[0].size(); // Initialize the mini matrix vector mini(m, vector(n, 0)); // Row-wise trapping water for (int i = 0; i < m ; i++) { vector temp = heightMap[i]; vector trappedRow = trap(temp); for (int j = 0; j < n; j++) { mini[i][j] = trappedRow[j]; } } // Column-wise trapping water for (int j = 0; j < n; j++) { vector temp; for (int i = 0; i < m; i++) { temp.push_back(heightMap[i][j]); } vector trappedCol = trap(temp); for (int i = 0; i < m; i++) { mini[i][j] = min(mini[i][j], trappedCol[i]); } } // Calculate the total water trapped int ans = 0; for (int i = 0; i < m ; i++) { for (int j = 0; j < n ; j++) { ans += mini[i][j]; } } return ans; } }; ....................................................................................................... IT is giving wrong ans heightMap = [[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]] Use Testcase Output 15 Expected 14 .......................
Bhaiya aap please contest ke questions ka bhi solution provide karo na kyuki easy vale hojate hai and medium vala sirf brute force se hota hai jo TLE de deta hai. And bakiyo ke video dekhta hu to vo direct solution hi bata dete hai. TO question solve karte walqt feel nahi aati.
hey, great explanation! just had a small doubt, at around 30:15, when we started filling water from Boundary cell (0,3)=1, we filled water at (1,2)=1 and then (1,1)=2, we were able to fill because the boundary cell (1,0)=3, which is greater than 2 & 1. But here, we didn't even looked at the value present at boundary cell (1,0), in our input it's 3, but it could be let's say 1. In that case we won't be able to trap water. So, I want to understand how was you sure that the Boundary cell (1,0) will be greater than 2 & 1? Please excuse if I am missing something, I am just thinking on that part. Thanks
Basically, all the smaller heights and their neighbours would have already been processed and no such case would arise. I had the same doubt, but to understand this better I would suggest that you dry run the code on your test case and you'll figure it out too. The visualization is a bit misleading because it looks like DFS, but that's not how the algorithm is working.
@java_bitbybit i am also facing the same doubt ...and i can't able to visualize how it's going so smoothly, if you understood please clear it to me as well
Bhai, aapne kyse soncha hai ye solution. Mai ek saal se kaar raha hu DSA leking fir bhi nahi kaar paya ye solution, kabhi kabhi toh approach hi nahi aati hai, please yaar bata do na agar kuch tip ho toh. Big fan of your approach.
Hello Sir, I have a doubt, like in rain water trapping-i, we follow the approach of finding water stored at any position is equal to min(preMax[i],sufMax[i])-arr[i]. Then why my approach for this question using min(min(topMax[i][j],bottomMax[i][j]),min(leftMax[i][j],rightMax[i][j]))-arr[i][j] doesn't work.
Java Solution: class Solution { public int trapRainWater(int[][] heightMap) { int n = heightMap.length; int m = heightMap[0].length; Queue pq = new PriorityQueue(new Comparator() { @Override public int compare(ArrayLista, ArrayListb){ return Integer.compare(a.get(0), b.get(0)); } }); boolean vis[][] = new boolean[n][m]; int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}}; //adding boundary columns into priority queue for(int j=0;j
Hy sir can we do it in same way we did trapping rain water one use previous greater and next greater it will take n*m time to find those prevGreater, next,up,down.. and then n*m so find how much water we can store on top of each block assuming 0 boundary here we can implement all the 4 function and then do it: can we do it this way class Solution { public int trapRainWater(int[][] heightMap) { int n = heightMap.length; int m = heightMap[0].length; int[][] nextGreater = new int[n][m]; int[][] previousGreater = new int[n][m]; int[][] downGreater = new int[m][n]; int[][] upGreater = new int[m][n]; for(int i = 0; i < n; i++){ fillNextGreater(i, nextGreater[i], heightMap); fillPreviousGreater(i, previousGreater[i], heightMap); } for(int j = 0; j < m; j++){ fillUpGreater(j, upGreater[i], heightMap); fillDownGreater(j, downGreater[i], heightMap); } } }
Bro I found this solution someone have posted this he has solved it using dp with complexity of n2 class Solution { public int trapRainWater(int[][] heightMap) { int rows = heightMap.length; // Number of rows int cols = heightMap[0].length; // Number of columns int[][] waterLevels = new int[rows][cols]; // Maximum water levels at each cell // Initialize waterLevels with heightMap values for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { waterLevels[row][col] = heightMap[row][col]; } }
Thank you LEGEND, no one explains better than you. you made this hard easy and I got it within 15 minutes.
Means a lot ❤️🙏
I am jealous of those who will come to know about MIK in their 1st year of college. It is a treasure they will realise
me too vro , got to know after B-tech🙃, isliye reach kam hai bhai , log chhupane k chakkar me share hi nahi krrhe channel😂
MIK you are a legend have a small request please start solving contest problems no one is doing that properly. Anyone else feel the same like this I will try to post this comment everyday so that MIK listens to our request.
Everyone can explain easy concepts, but the true caliber of a teacher can be understood when he teaches complex topics like these. Hats off!
Frankly, I was confused when I saw the example test case diagram and hit a mental roadblock.
Your explanations are truly outstanding! You’ve made everything so easy to understand, and not only that, your help has been invaluable. May God bless you. You are a true nationalist, supporting all sections of society without expecting anything in return. You are an inspiration to the younger generation. I believe that your UA-cam channel will become extremely popular, and I pray for your success. Thank you so much a true Indian, a true nationalist, and a real hero for the youth!
you make the hard questions look easy,
keep it up
I initially thought, ki kuch volume wagrah calculate karna hoga 🥹
32:48 is what makes you different from others.
There is a big difference between feeding concepts and teaching concepts.
I watched neetcode and some others videos in the morning and decided to wait for you.
my doubts, and my all answers are always answered in your videos.
After understanding the concept, I was able to write the code by myself. Thank you so much for your great explanation!
Baadshaah ho sir aap DSA k. Itna mast samajh me aya hai.
your video + cooker city = sukoon
😂 true
cooker city kya hota hai?
@@coldcoke9254 jisme sabzi banti he , search in you tube how to make sabzi in cooker
Thank you bhaiya for the awesome explanation.
superb explanation. if they ask you this question most probably they do not want to hire you
Indeed you are far far better than other famous UA-camrs who teach DSA 👍🏻
Bhaiya truly speaking from my heart, if DSA teaching is an art, You are the artist, Every time I watch your videos I got amazed by the clarity with which you explain. This world definitely needs more and more artist like you.❤❤
Take a bow man!🙌🙌
Bhai kaafi mehnat karte ho aap apni videos me really commendable 🙏🙏
Bro you are the GOAT. Any plans on recording a LLD playlist please MIK. We as freshers want to learn LLD and I can't find any trusted resources for it.
Yes LLD is planned in near future. Stay tuned ❤️❤️🙏🙏
Will you know MIK you are giving such awesome content for not even a single penny of charge, Thanks for the explaining the questions in this way, really market is full of earning money oriented but you are providing better than those all. Thanks
Thank you sooo much MIK, for covering JAVA code too!! :)
BHAI PLEASE Contest ke 3rd and 4th question ki vedios bhi banaya karo khi soln nhi milte achhe
Sure thing , i am going back to home today evening.
Let me find some time this week ❤️🙏
Gfg ka contest ka bhi solution kar dijiyega bhaiya,,,koi achha solution nehi he @@codestorywithMIK
Leetcode Contest video solution in case you want ua-cam.com/video/oAhlTS7U8GM/v-deo.html&ab_channel=KumarK%5BAmazon%5D
@@bikram3249 bhai sir ke pass itna time nhi hota,... unki respect karo..... leetcode bahut hai kyokni vo comman hai...nhi to phir koi tisra aayega.. or us platform ka name leke bolega....leetcode ki problem acchi hoti hai in contest so sir vo hi karde to bhaut hai
@@codestorywithMIK hnn sir please banaya karo
was a good question tried to solve it using monotonic stack approach by figuring out minimum max height from all 4 directions and then subtracting the current height and ignoring boundary values and it worked for 17 cases but was not correct approach after all.
Thanks for the video
You are the GEM😩🙇♂😩...Please solve contest ques also🙇♂🙇♂
yes please sir make a contest solution video
Yes sir please
😂 tell him to write your oa also 😂😂😂
Hi Mik bhai, I dont know if everyone needs to hear this or not but the 1st approach that came to my mind is to apply trapping rain water 1 column wise and then from top to bottom. Even after trying for a long long time, I failed to submit it, bcz i was getting wrong answer continuously and unable to understand why. Its almost the same approach right. Idk if i was thinking like that but ultimately bcz of this failed try, i got to understand why this approach will not work in trapping rain water 2 and i think thats my greatest victory today, even bigger than the actual submission. Failed approach ne maza dila diya.😀
❤️👍🏻👌
Thanks for your immense effort, sir. Learning a lot from you 😊
U and TechDose are the best teachers of DSA
Very nice explanation. Thanks alot 🙂
Thankyou Mik Bhaiyaa 80 times(PS: my current Streak, trying to make it 3 digit)
tomorrows quote from my side:- “When you have a hard life, a tough life, success becomes very easy.”
Great explanation as always!!!
my friend was asked this ques in qualcomm in on-campus technical interview
Present sir
Aapka hi intezar tha Goat.
MIK Sirji 🫡
Thanks a lot !
Sir, thanks for this awesome lecture, there is a humble request from my side , if possible make a video on sliding window median , leetcode-480, again thank you so much for making DSA super easy.
Tomorrow's motivation:
Don’t seek motivation outside, become the spark that lights your own path.
for whom who are getting confuse that whet if any neighbouring cell is lower than the current cell ....then please observe that we already starting from the minimum from boundary cells so if you observe then the algorithm will automatically manage this situation
Cool 👌🏻
int waterlevel = min(maxleft, maxright ,maxup, maxdown) ;
if (water>=heightMap[i][j]){
totalwater += waterlevel - heightMap[i][j];
} where 1=
Thanks bhai
brilliant explanation. can you please also upload leetcode contest solutions
kafi sundar🤌
MIK bhai, aapne trapping rain water part1 stack se nahi banaya tha,
please make it when you get free time...
Sure thing , i am going back to home today evening.
Let me find some time this week ❤️🙏
First comment sir
Please make video on Yesterday's Biweekly Q3 and Q4. And today's weekly Q2, Q3 and Q4.
Sure thing , i am going back to home today evening.
Let me find some time this week ❤️🙏
@@codestorywithMIK Thank you so much! Thanks for the above video, the explanation was great specially the reasoning behind why we need to use heap :)
Leetcode Contest video solution in case you want ua-cam.com/video/oAhlTS7U8GM/v-deo.html&ab_channel=KumarK%5BAmazon%5D
tomorrows motivation : opportunities hit the door of the person who word hard and i will work very very hard
You are just one decision away from a totally different life
sir agar aap mujhe first year me mil gye hote to aaj me maang me placed hota🙂
Motivation for tomorrow - All it takes to change the course of the history is the will of a single men.
Bhai can u make neetcode 150 solutions in a separate playlist? ik most of em r already done by u but some of em are left out also neetcode explains in python but most of us need in c++ and there is no one better than u in c++ explanation. So kindly make a playlist for the solutions of neetcode150
class Solution {
public:
int FindEdges(vector& heightMap, int i, int j, int n, int m) {
int current = heightMap[i][j];
int top = 0, bottom = 0, left = 0, right = 0;
for (int t = i - 1; t >= 0; t--) {
top = max(top, heightMap[t][j]);
}
\
for (int t = i + 1; t < n; t++) {
bottom = max(bottom, heightMap[t][j]);
}
for (int t = j - 1; t >= 0; t--) {
left = max(left, heightMap[i][t]);
}
for (int t = j + 1; t < m; t++) {
right = max(right, heightMap[i][t]);
}
return min({left, right, top, bottom});
}
int trapRainWater(vector& heightMap) {
int n = heightMap.size();
int m = heightMap[0].size();
int units = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int mini = FindEdges(heightMap, i, j, n, m);
if (mini > heightMap[i][j]) {
units += (mini - heightMap[i][j]);
}
}
}
return units;
}
};
I tried solving this question by this logic but it failed in some test case, can anyone tell me what's wrong?
thanks
mik sir please solve contest questions also , please please
MIK sir I thought of applying traping water of 1D , 1st row wise then col wise and took the min of both ..
pleased tell why this logic is wrong🧠..
class Solution {
vector trap(vector &arr) {
int n = arr.size();
vector prefix(n), suffix(n), waterTrapped(n, 0);
// Build prefix array
prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix[i] = max(prefix[i - 1], arr[i]);
}
// Build suffix array
suffix[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffix[i] = max(suffix[i + 1], arr[i]);
}
// Calculate trapped water for each index
for (int i = 0; i < n; i++) {
waterTrapped[i] = min(prefix[i], suffix[i]) - arr[i];
}
return waterTrapped;
}
public:
int trapRainWater(vector &heightMap) {
int m = heightMap.size();
int n = heightMap[0].size();
// Initialize the mini matrix
vector mini(m, vector(n, 0));
// Row-wise trapping water
for (int i = 0; i < m ; i++) {
vector temp = heightMap[i];
vector trappedRow = trap(temp);
for (int j = 0; j < n; j++) {
mini[i][j] = trappedRow[j];
}
}
// Column-wise trapping water
for (int j = 0; j < n; j++) {
vector temp;
for (int i = 0; i < m; i++) {
temp.push_back(heightMap[i][j]);
}
vector trappedCol = trap(temp);
for (int i = 0; i < m; i++) {
mini[i][j] = min(mini[i][j], trappedCol[i]);
}
}
// Calculate the total water trapped
int ans = 0;
for (int i = 0; i < m ; i++) {
for (int j = 0; j < n ; j++) {
ans += mini[i][j];
}
}
return ans;
}
};
.......................................................................................................
IT is giving wrong ans
heightMap =
[[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]]
Use Testcase
Output
15
Expected
14
.......................
sir can you also start a series for the leetcode questions...
693 days streak 😶🌫😶🌫 Damn sir
Bhaiya coding skills toh seekha de rahe ho , but speaking skills ke liye kuch tips ya kese practice kare wo bata dijiye na koi video me
Bhaiya aap please contest ke questions ka bhi solution provide karo na kyuki easy vale hojate hai and medium vala sirf brute force se hota hai jo TLE de deta hai. And bakiyo ke video dekhta hu to vo direct solution hi bata dete hai. TO question solve karte walqt feel nahi aati.
hey, great explanation! just had a small doubt, at around 30:15, when we started filling water from Boundary cell (0,3)=1, we filled water at (1,2)=1 and then (1,1)=2, we were able to fill because the boundary cell (1,0)=3, which is greater than 2 & 1. But here, we didn't even looked at the value present at boundary cell (1,0), in our input it's 3, but it could be let's say 1. In that case we won't be able to trap water. So, I want to understand how was you sure that the Boundary cell (1,0) will be greater than 2 & 1? Please excuse if I am missing something, I am just thinking on that part.
Thanks
Basically, all the smaller heights and their neighbours would have already been processed and no such case would arise.
I had the same doubt, but to understand this better I would suggest that you dry run the code on your test case and you'll figure it out too. The visualization is a bit misleading because it looks like DFS, but that's not how the algorithm is working.
@java_bitbybit i am also facing the same doubt ...and i can't able to visualize how it's going so smoothly, if you understood please clear it to me as well
Actually visualize karna hi bada tough hai yaar. imagination bhi mushkil hai ki flow kaise bhaag raha hai.
@ If you can explain what you understood, may be I can suggest where you are getting it wrong.
Mike,,,please post solutions of the contest too....
Sure thing , i am going back to home today evening.
Let me find some time this week ❤️🙏
Leetcode Contest video solution in case you want ua-cam.com/video/oAhlTS7U8GM/v-deo.html&ab_channel=KumarK%5BAmazon%5D
Bhai, aapne kyse soncha hai ye solution. Mai ek saal se kaar raha hu DSA leking fir bhi nahi kaar paya ye solution, kabhi kabhi toh approach hi nahi aati hai, please yaar bata do na agar kuch tip ho toh. Big fan of your approach.
Hello Sir,
I have a doubt, like in rain water trapping-i, we follow the approach of finding water stored at any position is equal to min(preMax[i],sufMax[i])-arr[i].
Then why my approach for this question using min(min(topMax[i][j],bottomMax[i][j]),min(leftMax[i][j],rightMax[i][j]))-arr[i][j] doesn't work.
Petation for contest q2,q3,q4 please
Sure thing , i am going back to home today evening.
Let me find some time this week ❤️🙏
Leetcode Contest video solution in case you want ua-cam.com/video/oAhlTS7U8GM/v-deo.html&ab_channel=KumarK%5BAmazon%5D
@@codestorywithMIK 💌
Which tab you use to create the slides?
bhaiya plz make video on the leetcode contest solutions plz humble request
Please sir give the solution of contest problem also 😅😅
Sure thing , i am going back to home today evening.
Let me find some time this week ❤️🙏
Leetcode Contest video solution in case you want ua-cam.com/video/oAhlTS7U8GM/v-deo.html&ab_channel=KumarK%5BAmazon%5D
Java Solution:
class Solution {
public int trapRainWater(int[][] heightMap) {
int n = heightMap.length;
int m = heightMap[0].length;
Queue pq = new PriorityQueue(new Comparator() {
@Override
public int compare(ArrayLista, ArrayListb){
return Integer.compare(a.get(0), b.get(0));
}
});
boolean vis[][] = new boolean[n][m];
int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
//adding boundary columns into priority queue
for(int j=0;j
Bro can you give problem sheet of all main topics of medium level for placement
Please make a videos on english😢😢😢
bhai captions use karlo but hindi is very easy to understand things in depth. please
@@wearevacationuncoverers han bro hindi me hi shi rhega apni native language hai to depth me jyada samjh aat hai,..
You dont updated the dsa list sir??
Thanks for the djikstra algoo❤❤❤❤❤
Complete list coming soon.
This is draft - ua-cam.com/users/postUgkxOYOEbwRwooVVxPTF_PA37SMxM4eda5Na?si=1sKWvIiMwAN0TgJS
3rd view sir
TS code -
function trapRainWater(heightMap: number[][]): number {
let m = heightMap.length;
let n = heightMap[0].length;
//defineing priority queue with min priority
const boundaryCells: { height: number, row: number, col: number}[] = [];
const enqueue = (height: number, row: number, col: number) => {
boundaryCells.push({height, row, col});
boundaryCells.sort((a, b) => a.height - b.height); //Min-Heap
}
const dequeue = () => boundaryCells.shift();
const visited: boolean[][] = Array.from({length: m}, ()=> Array(n).fill(false));
//Adding Boundary ele
for(let row = 0; row < m ; row++){
enqueue(heightMap[row][0], row, 0);
visited[row][0] = true;
enqueue(heightMap[row][n-1], row, n-1);
visited[row][n-1] = true;
}
for(let col = 0; col < n ; col++){
enqueue(heightMap[0][col], 0, col);
visited[0][col] = true;
enqueue(heightMap[m-1][col], m-1, col);
visited[m-1][col] = true;
}
let water = 0;
const directions = [
[0,-1], [0,1], [-1, 0], [1,0]
];
while(boundaryCells.length > 0){
const cell = dequeue()!;
const {height, row, col} = cell;
for(const [dx, dy] of directions){
const i = row+dx;
const j = col+dy;
if (i >= 0 && i < m && j >= 0 && j < n && !visited[i][j]){
water += Math.max(height - heightMap[i][j], 0);
enqueue(Math.max(height, heightMap[i][j]), i , j);
visited[i][j] = true;
}
}
}
return water;
};
Hy sir can we do it in same way we did trapping rain water one use previous greater and next greater it will take n*m time to find those prevGreater, next,up,down.. and then n*m so find how much water we can store on top of each block assuming 0 boundary here we can implement all the 4 function and then do it:
can we do it this way
class Solution {
public int trapRainWater(int[][] heightMap) {
int n = heightMap.length;
int m = heightMap[0].length;
int[][] nextGreater = new int[n][m];
int[][] previousGreater = new int[n][m];
int[][] downGreater = new int[m][n];
int[][] upGreater = new int[m][n];
for(int i = 0; i < n; i++){
fillNextGreater(i, nextGreater[i], heightMap);
fillPreviousGreater(i, previousGreater[i], heightMap);
}
for(int j = 0; j < m; j++){
fillUpGreater(j, upGreater[i], heightMap);
fillDownGreater(j, downGreater[i], heightMap);
}
}
}
Dsa hard nahi tha bas samzane wale galat the all othere teachers…..
❤️🙏
Tcs codevita 2025 when will start? Can anyone tell
kab ho rha start
Bro I found this solution someone have posted this he has solved it using dp with complexity of n2
class Solution {
public int trapRainWater(int[][] heightMap) {
int rows = heightMap.length; // Number of rows
int cols = heightMap[0].length; // Number of columns
int[][] waterLevels = new int[rows][cols]; // Maximum water levels at each cell
// Initialize waterLevels with heightMap values
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
waterLevels[row][col] = heightMap[row][col];
}
}
boolean updated = true;
boolean initialPass = true;
while (updated) {
updated = false;
// First pass: top-left to bottom-right
for (int row = 1; row < rows - 1; row++) {
for (int col = 1; col < cols - 1; col++) {
int potentialWaterLevel = Math.max(heightMap[row][col],
Math.min(waterLevels[row - 1][col], waterLevels[row][col - 1]));
if (initialPass || waterLevels[row][col] > potentialWaterLevel) {
waterLevels[row][col] = potentialWaterLevel;
updated = true;
}
}
}
initialPass = false;
// Second pass: bottom-right to top-left
for (int row = rows - 2; row >= 1; row--) {
for (int col = cols - 2; col >= 1; col--) {
int potentialWaterLevel = Math.max(heightMap[row][col],
Math.min(waterLevels[row + 1][col], waterLevels[row][col + 1]));
if (waterLevels[row][col] > potentialWaterLevel) {
waterLevels[row][col] = potentialWaterLevel;
updated = true;
}
}
}
}
int totalWaterTrapped = 0;
// Calculate total trapped water
for (int row = 1; row < rows - 1; row++) {
for (int col = 1; col < cols - 1; col++) {
if (waterLevels[row][col] > heightMap[row][col]) {
totalWaterTrapped += waterLevels[row][col] - heightMap[row][col];
}
}
}
return totalWaterTrapped;
}
}
Petation for contest q2,q3,q4 please ⬆ ⬆ ⬆
Sure thing , i am going back to home today evening.
Let me find some time this week ❤️🙏
Leetcode Contest video solution in case you want ua-cam.com/video/oAhlTS7U8GM/v-deo.html&ab_channel=KumarK%5BAmazon%5D
@@ananyeagarwal9770 bro, have you purchased his course?
26:10 bhai apni height to dekh pehle
😂😂😂
thanku sir