Most of the times(mostly when I see a tough question), I see your video and I exclaim "WOWWW!" and hit the like button. Great work! Thanks a ton for your videos.
00:04 Maximal Rectangle problem 01:39 Concept of largest rectangle in histogram 03:09 Understanding maximal rectangle in histograms through example 04:40 Optimizing complexity using prefix sum concept 06:04 Understanding and visualizing histogram bar heights 07:33 Prefix sum computation for histogram bar preparation 08:59 Compute maximal rectangle area using stack and queue 10:34 Time complexity analysis for computing maximal rectangle area.
Sometimes you just need a hint to solve a question, in this question as soon as strive said that largest rectangle in the histogram, I paused the video and solve the question myself.
cpp solution class Solution { public: int maximalRectangle(vector& matrix) { int n = matrix.size(); int m = matrix[0].size(); int maxiarea = 0; vector presum(n, vector(m, 0)); for (int j = 0; j < m; j++) { int sum = 0; for (int i = 0; i < n; i++) { if (matrix[i][j] == '1') { sum += 1; } else { sum = 0; } presum[i][j] = sum; } } for (int i = 0; i < n; i++) { maxiarea = max(maxiarea, lhist(presum[i])); } return maxiarea; } int lhist(vector& heights) { stack st; int max_area = 0; int n = heights.size();
We don't actually need to create the sum variable it can also be done as for (int c = 0; c < m; c++) { for (int r = 0; r < n; r++) { if (matrix[r][c] == '1') { if (r != 0) dp[r][c] = dp[r - 1][c] + 1; else dp[r][c] = 1; } else dp[r][c] = 0; } }
Most of the times(mostly when I see a tough question), I see your video and I exclaim "WOWWW!" and hit the like button.
Great work!
Thanks a ton for your videos.
The visualisation of this question was the key cracking point here, I couldn't think about it
if you don't want to use Prefix Sum for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == '1') {
arr[j]++;
} else {
arr[j] = 0;
}
}
maxArea = Math.max(maxArea, largestRectangleArea(arr));
}
great work sir, thanks a tonn❤, i watch your videos on a regular basis along with my homie, honestly she has such a huge ass crush on you lmao.
00:04 Maximal Rectangle problem
01:39 Concept of largest rectangle in histogram
03:09 Understanding maximal rectangle in histograms through example
04:40 Optimizing complexity using prefix sum concept
06:04 Understanding and visualizing histogram bar heights
07:33 Prefix sum computation for histogram bar preparation
08:59 Compute maximal rectangle area using stack and queue
10:34 Time complexity analysis for computing maximal rectangle area.
Very nice explanation Striver. Eagerly waiting for strings
Understood Bhaiya!!
Sometimes you just need a hint to solve a question, in this question as soon as strive said that largest rectangle in the histogram, I paused the video and solve the question myself.
finally got the question thanks for the help
superb 🎉
class Solution {
public:
int maxInHistogram(vector& arr) {
int n = arr.size();
int maxi = 0;
stack st;
arr.push_back(0);
for (int i = 0; i < arr.size(); ++i) {
while (!st.empty() && arr[st.top()] >= arr[i]) {
int height = arr[st.top()];
st.pop();
int width = st.empty() ? i : i - st.top() - 1;
maxi = max(maxi, height * width);
}
st.push(i);
}
return maxi;
}
int maximalRectangle(vector& matrix) {
int r = matrix.size();
if(r == 0) return 0;
int c = matrix[0].size();
vector ps(c,0);
int maxi = 0;
for(int i = 0; i < r; ++i){
for(int j = 0; j < c; ++j){
if(matrix[i][j] == '1') ps[j]++;
if(matrix[i][j] == '0') ps[j] = 0;
}
maxi = max(maxi, maxInHistogram(ps));
}
return maxi;
}
};
//arr[i] * (nse - pse - 1)
superb , Thank you
Thank You sirr
I think the space complexity should be O(n*m) + O(n*m) as we are using the stack of size m, n times.... Correct me if I am wrong.
you are correct
Thank you so much.Understood Bhaiya
Thanks
space should be O(n*m) +O(m) na ? why O(n) can anyone explain?
Right 👍
yup
coz, running a loop for n elements (row) that's why O(N)
O(n) for using stack in Largesthistogram function. okay?
UNDERSTOOD;
Thanks a lot
Understood
wowwwwwww Understood
cpp solution
class Solution {
public:
int maximalRectangle(vector& matrix) {
int n = matrix.size();
int m = matrix[0].size();
int maxiarea = 0;
vector presum(n, vector(m, 0));
for (int j = 0; j < m; j++) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (matrix[i][j] == '1') {
sum += 1;
} else {
sum = 0;
}
presum[i][j] = sum;
}
}
for (int i = 0; i < n; i++) {
maxiarea = max(maxiarea, lhist(presum[i]));
}
return maxiarea;
}
int lhist(vector& heights) {
stack st;
int max_area = 0;
int n = heights.size();
for (int i = 0; i
We don't actually need to create the sum variable it can also be done as
for (int c = 0; c < m; c++)
{
for (int r = 0; r < n; r++)
{
if (matrix[r][c] == '1')
{
if (r != 0)
dp[r][c] = dp[r - 1][c] + 1;
else
dp[r][c] = 1;
}
else
dp[r][c] = 0;
}
}
very hard
yooooo big fan !!!
What is the song in the end
inspiration
❤
Understood
❤