CORRECTION IN TIME COMPLEXITY : The time complexity of the `maximalRectangle` function is dominated by the `MAH` function, which in turn relies on `NSR` and `NSL` -> See below 1. `NSR` (Next Smaller to Right) and `NSL` (Next Smaller to Left): - Both `NSR` and `NSL` functions use a stack to find the next smaller element to the right and left, respectively. - In the worst-case scenario, each element may be pushed and popped from the stack once, leading to a time complexity of O(n) for each function, where n is the number of elements in the input vector `heights`. 2. `MAH` (Maximum Area Histogram): - `MAH` calls both `NSR` and `NSL`, each of which has a time complexity of O(n). - Constructing the `width` vector involves iterating over each element once, which also has a time complexity of O(n). - Therefore, the overall time complexity of `MAH` is O(n). 3. `maximalRectangle`: - The `maximalRectangle` function iterates through each row of the input matrix. - For each row, it updates the `height` vector and calculates the maximum area histogram using the `MAH` function. - Since there are m columns in each row and n rows in total, the overall time complexity of `maximalRectangle` is O(n * m). Combining all these analyses, the overall time complexity of the given solution is O(n * m).
Just because of this video I am able to solve 3 other Qns : 1. Largest Rectangle in Histogram (Leetcode Hard) 2. Next Smaller Element (GFG) - NSR 3. Smallest number on left (GFG) - NSL Thanks to the LEGEND MIK
You will soon be extremely viral and almost everyone in India (coding community specially) will know this legend. mind blowing content and hats off to your patience in covering every detail
Usually i dont commment on videos but todays video oh ho i was not able to stop myself from commenting So much thank you a very great explanantion and rellay informative every minute was worth !!! hope we will meet soon
bhai bhott jaada mzaa aaya .................... mtlb m abhi b soch rha ki kya mzedaar solution hai..thanks mik❤❤ mene to hidden ques solve kiye the pehle pr mai isko MAP nahi kr paaya unn problem se .
hidden qustion ko har row me apply kar dete to easily ho jata. bas har row ko 1-D array me convert karna hai heights ko dhyan me rkh ke ki zero hogi ya add hogi upar wali row ki height.
I watched some other TH-camrs' videos; they created ten to twenty minute videos just to give us the code for this problem. They made no attempt to develop intuition to solve this problem. However, congrats! For a video that lasts one and a half hours, you covered too much information in it. With this, we hope to gain a thorough grasp of the issues.
thanks for the explaination I have many doubts :) first dekhna padega video araam se kabhi last doubt clear ho gaya.... NSL ke 0th and n-1th index mai hamesha -1 hi rahega?? and for NSR 0th and n-1th index mai n rahega hamesha??....... while calucating widtth, agar height[i] 0 nahi hua toh e.g matrix[0][4] = 1 hota and matrix[1][4]= 0, toh height toh 1 hoti .. but width array mai toh n hi rehta (n-(-1) -1 ) == n, can u please explain how the code is working for this scenario... --------------------------- also if possible can u explain the changes done in the simplified MAH solution , (better to make a pinned comment for that, might help others too )
Completed the whole lecture in nearly 1:45:00 minutes but when you ar writing i am able to write the next line of code in my mind before you start writing the line and able to find all the silly mistakes that you done during code writing thanks bhaiya such a great explanation first i tried to understand this question from solutions section but unable to understand now i understand why we used stack for nsr and nsl how time Complexity reduced by stack you are gem bhaiya for us hatsoff 🫡🫡🫡🫡
why i call him god of dsa ?? 0. STORY TO CODE...jo stroy hai same code mein chap do 1.Always motivate 2.khandaani tarika 3.yahan pe dhyaan do acche se focus kro 4.leetcode pe hard mark hai lekin main aasan bana dunga 5.subproblems pe focus kro 6.Aur mehnat krte raho + + +
@@codestorywithMIKI mean for cell 2nd in row 1, i.e. matrix[1][2] it can also form a rectangle of 1 height and width 3, but according to the 1d array, it can max create a height of 2 and width of 1...the area thus being 2... See the time stamp 25:12, max area 2...but we can make a max area of 3 from that cell... That's my doubt.... Tha
I think i got your Qn. Yes but the area you are referring [1, 1, 1] will not be missed when we go further to [1][3] we will be considering that area of 3. So the approach makes sure that we don’t miss out any possible rectangle.
Bhaiya Aaj contest me basic dijkstra ka question tle mar gya,mere 5th attempt me submit hua,coz I know the visited implementation of dijkstra.But it ain't an optimization.Please make a video explaining the visited part when you get time. It's q3 of today's contest. Thank
I easily understand the logic and concept behind the question but if I tried the same question after some days, I completely forget that. I don't know how to overcome this problem
bhaiya how to revise DSA and make own notes please make video on it. ethne sare problem ke solution ke notes bnana fir usko revise karna possible nahi ho rha hai . thode dino bad dsa bhul rahi hu aisa lagta hai.
I'd suggest you make a note about the apporach used in a gist for each problem. You dont have to write the solution to each problem. If you have the mastery on a programming language and familiar with the collections framework(if youre a java /python user not sure if other languages have them or not) you'd be good be able to solve the problem on your own when you read the approach on which you made the note. After a few days you wont need that too and would immediately be able to solve the problem without referring to the notes
I agree with @ruchi . Try to make notes only of concepts. And revise concepts mostly instead of revising all Qns. Once your concepts are crystal clear, you can solve qns if it’s a new one or a preciously solved one
public int maximalRectangle(char[][]matrix){ if(matrix.length==0) return 0; int ans=0; int[]histo=new int[matrix[0].length]; for(char[]row:matrix){ for(int i=0;i
Uploaded. Added in video description also. iPad PDF Notes - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-85-Maximal%20Rectangle.pdf
@@codestorywithMIK bhaiya ek question tha bhaiya Maine theory kar liya hai aur aapke video dekh ke problem solve karta hu aur phir wahi problem revise karta hu par khud se bahut sare questions nhi hote please kuch bata dijiye ki kaise Karu kyo ki September se placement start hone wali hai
@CSERITIKSINGH Please always remember that this is a very common problem. It happens to almost everyone. There are of topics and concepts available and in order to keep them in mind, we will have to consistently solve Qns. Practicing on a daily basis is the key and make sure to focus on INTUITION
I usually try to make videos which can help beginners also. It’s from Ground Level Also, in this video, you will be able to solve 4 Hidden Problems, hence lengthy
MIK........I still can't believe I did this HARD question, in one go after just skimming your video. After solving: Is this question really HARD?? I doubt
CORRECTION IN TIME COMPLEXITY :
The time complexity of the `maximalRectangle` function is dominated by the `MAH` function, which in turn relies on `NSR` and `NSL` -> See below
1. `NSR` (Next Smaller to Right) and `NSL` (Next Smaller to Left):
- Both `NSR` and `NSL` functions use a stack to find the next smaller element to the right and left, respectively.
- In the worst-case scenario, each element may be pushed and popped from the stack once, leading to a time complexity of O(n) for each function, where n is the number of elements in the input vector `heights`.
2. `MAH` (Maximum Area Histogram):
- `MAH` calls both `NSR` and `NSL`, each of which has a time complexity of O(n).
- Constructing the `width` vector involves iterating over each element once, which also has a time complexity of O(n).
- Therefore, the overall time complexity of `MAH` is O(n).
3. `maximalRectangle`:
- The `maximalRectangle` function iterates through each row of the input matrix.
- For each row, it updates the `height` vector and calculates the maximum area histogram using the `MAH` function.
- Since there are m columns in each row and n rows in total, the overall time complexity of `maximalRectangle` is O(n * m).
Combining all these analyses, the overall time complexity of the given solution is O(n * m).
1.5 hour movie ❌ 80 minutes POTD ✅
Bhai khatam hi nhi ho rhi video
@@devmadaan5146 😂😂 2x pe dekh na bhai
Just because of this video I am able to solve 3 other Qns :
1. Largest Rectangle in Histogram (Leetcode Hard)
2. Next Smaller Element (GFG) - NSR
3. Smallest number on left (GFG) - NSL
Thanks to the LEGEND MIK
Thanks for the qns. Can you share the link of 2nd and 3rd
@@DevOpskagyaan just type on GeeksforGeeks bro don't be lazy
80 min ki itni detailed video bnana mazaak nahi. Hats off to you ❤❤
You will soon be extremely viral and almost everyone in India (coding community specially) will know this legend.
mind blowing content and hats off to your patience in covering every detail
1.2 hour Netflix ❌
1.2 hours codestorywithMIK ✅
"I believe Allah has blessed you, Alhamdulillah. The way you think and explain is truly remarkable. May you achieve great success, akhi."
Thank you for providing such a crystal clear explanation in simple way.
Usually i dont commment on videos but todays video oh ho i was not able to stop myself from commenting
So much thank you a very great explanantion and rellay informative
every minute was worth !!!
hope we will meet soon
Do it bro after your explanation. Got stuck on '0' part than came back to video, understand the particular part and then successfully submitted.
bhai bhott jaada mzaa aaya .................... mtlb m abhi b soch rha ki kya mzedaar solution hai..thanks mik❤❤
mene to hidden ques solve kiye the pehle pr mai isko MAP nahi kr paaya unn problem se .
hidden qustion ko har row me apply kar dete to easily ho jata. bas har row ko 1-D array me convert karna hai heights ko dhyan me rkh ke ki zero hogi ya add hogi upar wali row ki height.
hacker hai bhai hacker 😅 dimag hack karke concept dal detahai bohat easily (EXPLAINATION GOD) thank MIK sir ❤❤
I don't think you have any idea of how good you explain!! Amazing !!!
Mind blowing, piece of ART. 🔥🔥
Thank you for providing such great explanation in simple way.Kudos to your efforts.
Pure hardwork,patience and passion thanks mik bhaiya 😊
That is the best explanation I have ever seen. Please continue making such videos because you patiently provide each and every intuition
80mins of video having every minute worth a watch! thanks man! 🙏
aap GOD ho 🙏🙏🙏🙏🙏🙏🔥🔥🔥🔥🔥
Amazing Solution as usual!!! The way you breakdown the problem is underrated as hell. Thanks a lot!!
Bhaiya just because of you I was able to solve 3 questions including hard one in leetcode contest u have provided with immense confidence thank u ❤❤
So happy to hear this ❤️
Keep it up
Habibi!!
1 hr ki movie dekhne se acha aapka video dekhne mein maja ata hai bhaiya!!
Story se code likhna aapse sikh raha hu bhaiya!!❤
Even the Hard feels Easy. Every Minute is Worth
Really good problem...it helped to revise the previously learnt concept...really loved the way of solving problem from previously solved problem 😄
Thank you for the video. We are always indebted for your hard work
literally watched first 11 minutes and was able to solve on my own.
I watched some other TH-camrs' videos; they created ten to twenty minute videos just to give us the code for this problem. They made no attempt to develop intuition to solve this problem. However, congrats! For a video that lasts one and a half hours, you covered too much information in it. With this, we hope to gain a thorough grasp of the issues.
Thank you for clear explanation.
Kudos to those people who watched the video till end , you have utmost patience and bow down to CSwithmik
bhaiya tysm for the tutorials apki vdo quality bhut next level hai...I'm so grateful ki Ik about your channel... Apko bhut success mile
Man you are just on fire.
I was able to solve Leetcode - 84. Largest Rectangle in Histogram using this concept.
Thanks a lot
Better than Netflix 1 hour episodes.
Literally every second worth
pata hi nahi laga 1hr se lambi video thi
Mind blowing explanation 🔥
Bhaiya meet in the middle technique explain kar dijiye 2-3 question. It is more popular nowadays in online Assessment and interviews.
For approach 1 can we use priority queue to get NSL and NSR?
gr8!! thnks very helpful
koi aisa paid course me bhi nahi parahega bhai. guruji ❣
thanks for the explaination
I have many doubts :) first dekhna padega video araam se kabhi
last doubt clear ho gaya....
NSL ke 0th and n-1th index mai hamesha -1 hi rahega?? and for NSR 0th and n-1th index mai n rahega hamesha??.......
while calucating widtth, agar height[i] 0 nahi hua toh e.g matrix[0][4] = 1 hota and matrix[1][4]= 0, toh height toh 1 hoti .. but width array mai toh n hi rehta (n-(-1) -1 ) == n,
can u please explain how the code is working for this scenario...
---------------------------
also if possible can u explain the changes done in the simplified MAH solution ,
(better to make a pinned comment for that, might help others too )
Excellent man 🔥
Great 👍
Legend 🔥🔥🔥🔥
Thank you 🙏
Completed the whole lecture in nearly 1:45:00 minutes but when you ar writing i am able to write the next line of code in my mind before you start writing the line and able to find all the silly mistakes that you done during code writing thanks bhaiya such a great explanation first i tried to understand this question from solutions section but unable to understand now i understand why we used stack for nsr and nsl how time Complexity reduced by stack you are gem bhaiya for us hatsoff 🫡🫡🫡🫡
Great explanation
Going through left and right would be 2n not n² dry run with many and submitted as well with that
Thanky You :)
Every question is hard until MIK gangsta walks in
Hey MIK , can you please make video on Leetcode 126 & 127 (Word Ladder 1 & 2 (Graph Series))
u r awsome
why i call him god of dsa ??
0. STORY TO CODE...jo stroy hai same code mein chap do
1.Always motivate
2.khandaani tarika
3.yahan pe dhyaan do acche se focus kro
4.leetcode pe hard mark hai lekin main aasan bana dunga
5.subproblems pe focus kro
6.Aur mehnat krte raho
+
+
+
Time complexity is O(m*(n+n)) which is same as O(m*n),,,, not O(m*n *n).
Correct me if I am wrong?
My bad. Let me add the correction in the Pinned comment.
You are right. Thank you
Bro make your DSA sheet
26:47
can't the max rectangle for row 0,1 2nd cell be 1x3 =3 also...
but per your logic it's 2 please clarify
For row 0,1,2
The maximum is 6
Notice the rectangle formed by below coordinates:
[1][2], [1][3], [1][4],
[2][2], [2][3], [2][4],
@@codestorywithMIKI mean for cell 2nd in row 1, i.e. matrix[1][2] it can also form a rectangle of 1 height and width 3, but according to the 1d array, it can max create a height of 2 and width of 1...the area thus being 2...
See the time stamp 25:12, max area 2...but we can make a max area of 3 from that cell...
That's my doubt....
Tha
I think i got your Qn.
Yes but the area you are referring [1, 1, 1] will not be missed when we go further to [1][3] we will be considering that area of 3.
So the approach makes sure that we don’t miss out any possible rectangle.
1 hour 20 minute video solution and bro called it EASY 💀
thankyou for the video, but please code it in java also it will be grateful
Please check the link in the video description. It has C++ and JAVA too 😇❤️🙏
Thanks a lot bhaiya ❤❤
bhaiya .. iske aur bhi approach hai kya ?
Thanks ❤❤❤❤❤
Maza Agya solution Dekhkar bhayanak Dimag kula ki problem kaise banaya jata ha
Thanks
epic
can you start gfg potd series also
it'll be very helpful
Is there any video for the second stack approach ?
Not yet Manoj.
But i will try to upload soon in my free times ❤️
Bhaiya Aaj contest me basic dijkstra ka question tle mar gya,mere 5th attempt me submit hua,coz I know the visited implementation of dijkstra.But it ain't an optimization.Please make a video explaining the visited part when you get time.
It's q3 of today's contest.
Thank
I easily understand the logic and concept behind the question but if I tried the same question after some days, I completely forget that. I don't know how to overcome this problem
One request bhai. Can u please try coding in java..
bhaiya how to revise DSA and make own notes please make video on it. ethne sare problem ke solution ke notes bnana fir usko revise karna possible nahi ho rha hai . thode dino bad dsa bhul rahi hu aisa lagta hai.
I'd suggest you make a note about the apporach used in a gist for each problem. You dont have to write the solution to each problem. If you have the mastery on a programming language and familiar with the collections framework(if youre a java /python user not sure if other languages have them or not) you'd be good be able to solve the problem on your own when you read the approach on which you made the note. After a few days you wont need that too and would immediately be able to solve the problem without referring to the notes
I agree with @ruchi .
Try to make notes only of concepts. And revise concepts mostly instead of revising all Qns.
Once your concepts are crystal clear, you can solve qns if it’s a new one or a preciously solved one
Mr. MIK please turn on your dark mode while you code .
Can't it will solved by dp ? As dp(i ,j) = max(dp(i,j) , dp(i-1 j) +dp(i , j-1) )
🙌
And also can anyone tell me how should one make notes for dsa
❤❤
🙇🏼♂🙇🏼♂🙇🏼♂
public int maximalRectangle(char[][]matrix){
if(matrix.length==0) return 0;
int ans=0;
int[]histo=new int[matrix[0].length];
for(char[]row:matrix){
for(int i=0;i
please bhaiya pdf bhi upload kar do
Yes, I will upload the PDF tonight ❤️❤️
@@codestorywithMIK ok bhaiya thanks you🙏
Uploaded. Added in video description also.
iPad PDF Notes - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-85-Maximal%20Rectangle.pdf
@@codestorywithMIK bhaiya ek question tha bhaiya Maine theory kar liya hai aur aapke video dekh ke problem solve karta hu aur phir wahi problem revise karta hu par khud se bahut sare questions nhi hote please kuch bata dijiye ki kaise Karu kyo ki September se placement start hone wali hai
@CSERITIKSINGH Please always remember that this is a very common problem. It happens to almost everyone. There are of topics and concepts available and in order to keep them in mind, we will have to consistently solve Qns. Practicing on a daily basis is the key and make sure to focus on INTUITION
Building kya hava mai udegi Kay ? 😂😂
Awaj hi nhi hain
Refresh the page. It happens sometimes .
This problem f*k my mind today
CodeStoryWithMik ❌
CodeMovieWithMik ✅
video is too much long. if 20-30 minutes duration, It’s good.
I usually try to make videos which can help beginners also.
It’s from Ground Level
Also, in this video, you will be able to solve 4 Hidden Problems, hence lengthy
Bro full intuition ke liye video long ho hi jati h or full dry run bhi to krwaate h jisse full concept clear hota h
Bro lambe lambe video dekhne me bahut majja aata he
Quick and incomplete knowledge se better hai lengthy and clear video which covers almost all angles of a problem.
MIK........I still can't believe I did this HARD question, in one go after just skimming your video.
After solving: Is this question really HARD?? I doubt
Great explanation