I am not sure whether you would be seeing this or not but I want to thank you for all the playlists (dp, graph, tree, recursion, placement series and the sde sheet) every content I have covered and just in 2 weeks literally just after giving proper 2 weeks to all the problems you have created I was able to clear all the amazon coding interviews. Not sure whether I would be able to clear the manegerial round but I have come so far because of the content you created. Not only amazon , Qualcomm, Vmware every where I am able to clear the rounds because solely of your content. Waiting for more content. Keep the great work going.
@@chinmaysharma1867 bhai thoda logical socho....koi tumhe aankh band karke bharosa karne ko nahi bolega, although these videos are very helpful but feel free to check other channels as well.
@Ayush Negi haan , bhai 2 weeks mei impossible hai noob se pro bnna .... But, Ye Banda Sunava Roy bol rha hai ..ki isne 2 week mei "every content " pdha hai , which is impossible ...maybe he is a liar ....mjhe to doubt hai ki isne Amazon bhi crack kra hai ki nhi ...ya phir likes paane ke liye jhooth likh dia
Those who are getting wrong answer in Leetcode , In the function they gave the 2d character vector(matrix) not integer vector , so instead of writing matrix[i][j]==1 write matrix[i][j]=='1' then everything will be fine
This problem came in my Internship test. Unfortunately, i was unable to solve it and scared from this question. My bad, i haven't look youtube at that time. Gladly, i found a mentor to teach me this.
didnt get the time complexity someone please clear a doubt , im using the part 1 code for the largest area function int largestRectangleArea(vector& heights) {
int n = heights.size(); stack st; vector PSE(n); vector NSE(n); for(int i = 0 ; i < n ; i++){ while(!st.empty() && heights[st.top()] >= heights[i]){ st.pop(); } PSE[i] = st.empty() ? -1 : st.top(); st.push(i);
} while(!st.empty()) st.pop(); for(int i = n-1 ; i >= 0 ; i--){ while(!st.empty() && heights[st.top()] >= heights[i]){ st.pop(); } NSE[i] = st.empty() ? n : st.top(); st.push(i);
@@DR-mq1le hello friend!!! there nesting not occuring thrice.see the loops correctly in first for loop inside 2 for loops written separately(i mean to say that they are not nested i.e., 2 &3 for loop) .
I think the time complexity would be O(n*m) + O(n*O(m)) O(n*m) because there are 2 loops and O(n* m) is for finding max area in histogram for each row and there are total n rows.
In case, if you are curious to solve using Recursive Solution:: Here is the memoized recursive solution(in JAVA):- (I HAVE ABSTRACT OUT THE MAX HISTOGRAM FUNCTION) :-) public int maximalRectangle(char[][] matrix) {
int[]dp = new int[matrix.length]; for(int i = 0; i < dp.length; i++) { dp[i] = -1; } int[]heights = new int[matrix[0].length]; return maxRec(0, matrix, heights, dp); } public int maxRec(int i, char[][] matrix, int[]heights, int[]dp) { if(i == matrix.length) {
@@takeUforward , can you please add some videos on DP on Graph & intervals please. I have followed your series, it is fantastic. But when I see a new problem, still I get stuck.
@@takeUforward . Can you please do one video on how to convert a back tracking problem like Coin change (from Recursion Play list), from Memoization to Tabulation DP please.
Hi Bhaiya, I am a 2022 graduate and i am currently working as a SRE intern at Cisco. I have an offer from Cisco for Site Reliability Engineer profile at a package of 15lpa and an offer from Fis Global for software engineer1 profile at a package of 11 lpa. Can you please advise me on what should I join. Also can I negotiate with Fis Global on the basis on Cisco offer as I am a new Graduate. I want to switch to Sde in the next one year in a top Mnc.I am worried that if join Cisco as Sre, it might hamper my chances when it will come to applying as Sde in companies like Amazon, Microsoft etc. I know in a long run Sre tag will lead to an Sre carrier, but I am not sure whether this really matter much if I want to switch to Sde in next one year itself.
didnt get the time complexity someone please clear a doubt , im using the part 1 code for the largest area function int largestRectangleArea(vector& heights) {
int n = heights.size(); stack st; vector PSE(n); vector NSE(n); for(int i = 0 ; i < n ; i++){ while(!st.empty() && heights[st.top()] >= heights[i]){ st.pop(); } PSE[i] = st.empty() ? -1 : st.top(); st.push(i);
} while(!st.empty()) st.pop(); for(int i = n-1 ; i >= 0 ; i--){ while(!st.empty() && heights[st.top()] >= heights[i]){ st.pop(); } NSE[i] = st.empty() ? n : st.top(); st.push(i);
bhai 2 months ka samay milega interview opportunity milne ke baad toh me pakka tera google interview crack kar lunga, ya sirf referral dila de WFH/WFO konsa bhi roles chalenge, Thank You brother in JEE advanced, please bhai
Bhai pata nhi exam ke din apne aap sick ho gaya tha, mujhe pata hai Medically and Anatomecally, kya hua tha per yaha bol nhi sakta hu yaar 😆😅😉😉😉, per mene gaand ghis ke din raat mehnat kiya tha bhai/behen @@skullcrusher33 , JAI HIND 😁. Salute and Respect to everybody who are running me,Thank You again
this is my solution which is giving wrong ans .. anyone please correct class Solution { public:
int f(vector& heights) { int n = heights.size(); stack st; int maxa = 0; for(int i=0;i= heights[i])) { int h = heights[st.top()]; st.pop(); int w ; if(st.empty() == true) w = i; else w = i - st.top() - 1;
maxa = max(maxa,h*w);
} st.push(i); } return maxa; }
int maximalRectangle(vector& matrix) { int n = matrix.size(); int m = matrix[0].size(); vector heights(m,0); int ans = 0; for(int i=0;i
matrix is of char type , just a subtle change if(matrix[i][j]=='1') h++; class Solution { public: int area(vectorheights,int n){ stackst; int maxi=0; for(int i=0;i=heights[i])){ int h=heights[st.top()]; st.pop(); int w; if(st.empty()){ w=i; } else w=i-st.top()-1; maxi=max(maxi,w*h); } st.push(i); } return maxi; } int maximalRectangle(vector& matrix) { int n=matrix.size();
int m=matrix[0].size(); int maxi=0; vectorstore(m,0); for(int i=0;i
The same code is giving wrong answer in leetcode. could someone help class Solution { public: int largestRectangleArea(vector &heights) { int n = heights.size(); stack < int > st; int leftsmall[n], rightsmall[n]; for (int i = 0; i < n; i++) { while (!st.empty() && heights[st.top()] >= heights[i]) { st.pop(); } if (st.empty()) leftsmall[i] = 0; else leftsmall[i] = st.top() + 1; st.push(i); } // clear the stack to be re-used while (!st.empty()) st.pop(); for (int i = n - 1; i >= 0; i--) { while (!st.empty() && heights[st.top()] >= heights[i]) st.pop(); if (st.empty()) rightsmall[i] = n - 1; else rightsmall[i] = st.top() - 1; st.push(i); } int maxA = 0; for (int i = 0; i < n; i++) { maxA = max(maxA, heights[i] * (rightsmall[i] - leftsmall[i] + 1)); } return maxA; } int maximalRectangle(vector& matrix) { int n = matrix.size(); int m = matrix[0].size(); vector h(m, 0); int maxArea = 0; for(int i=0; i
![Blox Fruits Dragon Rework Update [Full Stream]](http://i.ytimg.com/vi/EqDAp8udhm0/mqdefault.jpg)
I am not sure whether you would be seeing this or not but I want to thank you for all the playlists (dp, graph, tree, recursion, placement series and the sde sheet) every content I have covered and just in 2 weeks literally just after giving proper 2 weeks to all the problems you have created I was able to clear all the amazon coding interviews. Not sure whether I would be able to clear the manegerial round but I have come so far because of the content you created. Not only amazon , Qualcomm, Vmware every where I am able to clear the rounds because solely of your content. Waiting for more content. Keep the great work going.
@@chinmaysharma1867 bhai thoda logical socho....koi tumhe aankh band karke bharosa karne ko nahi bolega, although these videos are very helpful but feel free to check other channels as well.
It is impossible to crack within 2 weeks. You would have probably practiced before watching these videos.
only 2 weeks ?? U must be an Expert even before watching playlist
@Ayush Negi haan , bhai 2 weeks mei impossible hai noob se pro bnna .... But, Ye Banda Sunava Roy bol rha hai ..ki isne 2 week mei "every content " pdha hai , which is impossible ...maybe he is a liar ....mjhe to doubt hai ki isne Amazon bhi crack kra hai ki nhi ...ya phir likes paane ke liye jhooth likh dia
striver apni asli id se aaaa
Special thanks to you for making a clarification on why this problem is in DP playlist.
man am feeling proud of myself i was so consitent in this series of the dp. i watched i code every single question. thank you striver bhaiya...
Same brother 😀😀
Consistent**
Those who are getting wrong answer in Leetcode , In the function they gave the 2d character vector(matrix) not integer vector , so instead of writing matrix[i][j]==1 write matrix[i][j]=='1' then everything will be fine
Thanks!! Didn't notice it though 😅😅
This problem came in my Internship test. Unfortunately, i was unable to solve it and scared from this question. My bad, i haven't look youtube at that time. Gladly, i found a mentor to teach me this.
In the OA ? and How did you apply ?
@@tushar7305OA? What do you mean? Could you explain a bit?
Same here, got this question in Google Interview, i thought this was some Graph problem
@@alexlogan7330 I too thought it was a graph problem when I first saw it
Understood!! Thank you Striver for this amazing playlist and kudos to all the hard work you've put in to bring us this amazing content!!
UNDERSTOOD..........Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thanks striver for giving line of thinking that's the most difficult thing for me! Leap of faith🎉
Oh nice building up on previous concepts. Understood, thanks!
this blew my mind , on god , hats off man!
at 6:06 shouldn’t it be 3? there are 3 1’s together so 3*1=3
The time complexity will be O(n* (m+m)) instead of O(n*(m+n)). because the row size=m and size of height vector=m
Exactly what I was Thinking!
didnt get the time complexity someone please clear a doubt , im using the part 1 code for the largest area function
int largestRectangleArea(vector& heights) {
int n = heights.size();
stack st;
vector PSE(n);
vector NSE(n);
for(int i = 0 ; i < n ; i++){
while(!st.empty() && heights[st.top()] >= heights[i]){
st.pop();
}
PSE[i] = st.empty() ? -1 : st.top();
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n-1 ; i >= 0 ; i--){
while(!st.empty() && heights[st.top()] >= heights[i]){
st.pop();
}
NSE[i] = st.empty() ? n : st.top();
st.push(i);
}
int maxarea = 0;
for(int i = 0 ; i
@@DR-mq1le hello friend!!! there nesting not occuring thrice.see the loops correctly in first for loop inside 2 for loops written separately(i mean to say that they are not nested i.e., 2 &3 for loop) .
You have explained it very well sir, thanks for such a wonderful video
Understood! Thank you sooo much for your great work!!
Absolutely brilliant!! Great Job!!
I think the time complexity would be O(n*m) + O(n*O(m))
O(n*m) because there are 2 loops and O(n* m) is for finding max area in histogram for each row and there are total n rows.
No the max area in histogram is O(n) every element in height array is pushed and popped from stack only once
Thank you so much Striver
thank you striver.
beautifully explained
Thank you!
Understood!!!
Understood ❤❤❤
for max area of row 2...why won't it be 1x3 ??
Thankyou Sir. Understood
As always "understood" ❤️
Understood!!!Thank you
thanks a lot
Thankyou very much💚💚🙂
In case, if you are curious to solve using Recursive Solution:: Here is the memoized recursive solution(in JAVA):-
(I HAVE ABSTRACT OUT THE MAX HISTOGRAM FUNCTION) :-)
public int maximalRectangle(char[][] matrix) {
int[]dp = new int[matrix.length];
for(int i = 0; i < dp.length; i++)
{
dp[i] = -1;
}
int[]heights = new int[matrix[0].length];
return maxRec(0, matrix, heights, dp);
}
public int maxRec(int i, char[][] matrix, int[]heights, int[]dp)
{
if(i == matrix.length)
{
return 0;
}
if(dp[i] != -1)
{
return dp[i];
}
int[] temp = new int[heights.length];
for(int j = 0; j < heights.length; j++)
{
if(matrix[i][j] == '1')
{
heights[j]++;
// System.out.println("+1");
}
else
{
heights[j] = 0;
}
}
for(int k = 0; k < temp.length; k++)
{
temp[k] = heights[k];
}
int rec = maxRec(i + 1, matrix, heights, dp);
for(int k = 0; k < temp.length; k++)
{
heights[k] = temp[k];
}
int height = largestRectangleArea(heights);
int ans = Math.max(height, rec);
dp[i] = ans;
return ans;
}
understood!!!!
Brilliant.
max area of second row rect should be 3 not 2
understood sir, thank you very much
Thanks
understood
Understood Sir :)
love u striver bhaiya
The same code is giving wrong answer in leetcode. could someone help
BEST BEST BESTTTTT
Understood
You are best of the best
UNDERSTOOD ...
Brilliant!
Brother , how many more videos will be uploaded on the dynamic programming topic ?
Done
@@takeUforward it woud be great if you even cover dp on trees
@@takeUforward thanks for teaching me dp. mainly the thought process.
@@takeUforward , can you please add some videos on DP on Graph & intervals please. I have followed your series, it is fantastic. But when I see a new problem, still I get stuck.
@@takeUforward . Can you please do one video on how to convert a back tracking problem like Coin change (from Recursion Play list), from Memoization to Tabulation DP please.
Great Video
Hi Bhaiya, I am a 2022 graduate and i am currently working as a SRE intern at Cisco. I have an offer from Cisco for Site Reliability Engineer profile at a package of 15lpa and an offer from Fis Global for software engineer1 profile at a package of 11 lpa. Can you please advise me on what should I join. Also can I negotiate with Fis Global on the basis on Cisco offer as I am a new Graduate. I want to switch to Sde in the next one year in a top Mnc.I am worried that if join Cisco as Sre, it might hamper my chances when it will come to applying as Sde in companies like Amazon, Microsoft etc. I know in a long run Sre tag will lead to an Sre carrier, but I am not sure whether this really matter much if I want to switch to Sde in next one year itself.
whats ur status?
Today I came to know why all my seniors and batchmates, say about Striver . Such a beautiful explanation 🫡
Thankx
I feel this answer is there in leetcode discuss section
Understood❤
why this code giving tle on gfg
Understood 🥰
This is today’s lc problem 😅
Understood.
Understood 🖤
Understood Sir!
Understood Bhaiya
Understood..
understood!!
Understood !
didnt get the time complexity someone please clear a doubt , im using the part 1 code for the largest area function
int largestRectangleArea(vector& heights) {
int n = heights.size();
stack st;
vector PSE(n);
vector NSE(n);
for(int i = 0 ; i < n ; i++){
while(!st.empty() && heights[st.top()] >= heights[i]){
st.pop();
}
PSE[i] = st.empty() ? -1 : st.top();
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n-1 ; i >= 0 ; i--){
while(!st.empty() && heights[st.top()] >= heights[i]){
st.pop();
}
NSE[i] = st.empty() ? n : st.top();
st.push(i);
}
int maxarea = 0;
for(int i = 0 ; i
understood
Can't we solve this using simple DFS/BFS ??
It won't work , Dry run it
Understood
done
bhai 2 months ka samay milega interview opportunity milne ke baad toh me pakka tera google interview crack kar lunga, ya sirf referral dila de WFH/WFO konsa bhi roles chalenge, Thank You brother in JEE advanced, please bhai
lmao striver se referral maang rha h comments mai... aur thanks in jee advanced kya hota hai beh
Bhai pata nhi exam ke din apne aap sick ho gaya tha, mujhe pata hai Medically and Anatomecally, kya hua tha per yaha bol nhi sakta hu yaar 😆😅😉😉😉, per mene gaand ghis ke din raat mehnat kiya tha bhai/behen @@skullcrusher33 , JAI HIND 😁. Salute and Respect to everybody who are running me,Thank You again
Ab mera graduation Speech, jo aaplog banaenge, pura World Dekhega, again JAI HIND, per kitne baar bolna hai "JAI HIND"?
@@skullcrusher33 I think he is giving jee advanced exam , And that same time preparing for placement which is after 4 years.
UnderStood
6:06
💯💯💯
US!
8:13
US
Understood, thanks
❤️❤️❤️
❤️❤️❤️❤️❤️❤️❤️❤️
US❤
usus
Us
us
This is not a dp problem/solution. We are not calculating solution using previous solutions of sub problems
heights of rectangles are caluclated from previous row heights,hence dp
Space optimised dp you can say
us
WRONG APPROACH
the approach will fail for below input, its correct output should be 2 but is will give 1
[1,0]
[0,1]
Would you please explain how maximum area of rectangle is 2 ?
this is my solution which is giving wrong ans .. anyone please correct
class Solution {
public:
int f(vector& heights) {
int n = heights.size();
stack st;
int maxa = 0;
for(int i=0;i= heights[i]))
{
int h = heights[st.top()];
st.pop();
int w ;
if(st.empty() == true) w = i;
else w = i - st.top() - 1;
maxa = max(maxa,h*w);
}
st.push(i);
}
return maxa;
}
int maximalRectangle(vector& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector heights(m,0);
int ans = 0;
for(int i=0;i
matrix is of char type , just a subtle change if(matrix[i][j]=='1') h++;
class Solution {
public:
int area(vectorheights,int n){
stackst;
int maxi=0;
for(int i=0;i=heights[i])){
int h=heights[st.top()];
st.pop();
int w;
if(st.empty()){
w=i;
}
else
w=i-st.top()-1;
maxi=max(maxi,w*h);
}
st.push(i);
}
return maxi;
}
int maximalRectangle(vector& matrix) {
int n=matrix.size();
int m=matrix[0].size();
int maxi=0;
vectorstore(m,0);
for(int i=0;i
here you have to check if(matrix[i][j] == '1') as character 👍
@@Saurav_Kumar514 thanks man
its so good to see people reviewing each other's code.
The same code is giving wrong answer in leetcode. could someone help
class Solution {
public:
int largestRectangleArea(vector &heights) {
int n = heights.size();
stack < int > st;
int leftsmall[n], rightsmall[n];
for (int i = 0; i < n; i++) {
while (!st.empty() && heights[st.top()] >= heights[i]) {
st.pop();
}
if (st.empty())
leftsmall[i] = 0;
else
leftsmall[i] = st.top() + 1;
st.push(i);
}
// clear the stack to be re-used
while (!st.empty())
st.pop();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && heights[st.top()] >= heights[i])
st.pop();
if (st.empty())
rightsmall[i] = n - 1;
else
rightsmall[i] = st.top() - 1;
st.push(i);
}
int maxA = 0;
for (int i = 0; i < n; i++) {
maxA = max(maxA, heights[i] * (rightsmall[i] - leftsmall[i] + 1));
}
return maxA;
}
int maximalRectangle(vector& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector h(m, 0);
int maxArea = 0;
for(int i=0; i
ya whts the reason?
here you have to check if(matrix[i][j] == '1') as character 👍
Understood 🎉
understood
Understood
understood
Understood!
Understood
US❤️
us
understood
Understood
Understood!
understood
Understood
understood
Understood
understood