Program to Find Largest Rectangle in a Histogram
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int largestRectangle(vector<int> &heights)
{
int n = heights.size();
/* The stack holds indexes of heights[] array.
The bars stored in the stack are always in
increasing order of their heights.
*/
stack<int> currentStack;
// Initialize max area.
int maxArea = 0;
// To store the top of the stack.
int topOfStack = 0;
// To store an area with the top bar as the smallest bar.
int areaWithTop = 0;
// Run through all bars of a given histogram.
int i = 0;
while (i < n)
{
/* If this bar is higher than the bar on the top stack,
push it to stack.
*/
if (currentStack.empty() || heights[currentStack.top()] <= heights[i])
{
currentStack.push(i++);
}
else
{
/* Calculate the area with heights[topOfStack]
stack as the smallest bar.
*/
topOfStack = heights[currentStack.top()];
currentStack.pop();
areaWithTop = topOfStack * i;
if (!currentStack.empty())
areaWithTop = topOfStack * (i - currentStack.top() - 1);
maxArea = max(maxArea, areaWithTop);
}
}
/* Now pop the remaining bars from the stack and
calculate the area with every popped bar
as the smallest bar.
*/
while (!currentStack.empty())
{
topOfStack = heights[currentStack.top()];
currentStack.pop();
areaWithTop = topOfStack * i;
if (!currentStack.empty())
areaWithTop = topOfStack * (i - currentStack.top() - 1);
maxArea = max(maxArea, areaWithTop);
}
return maxArea;
}
int main()
{
int numHeights;
cout << "Enter number of heights: ";
cin >> numHeights;
vector<int> heights(numHeights);
cout << "Enter heights of the histogram\n";
for (int i = 0; i < numHeights; i++)
cin >> heights[i];
cout << "Area of largest rectangle in histogram: ";
cout << largestRectangle(heights);
}
Input
Enter number of heights: 3
Enter heights of the histogram
1 2 3
Output
Area of largest rectangle in histogram: 3
The algorithm to use the ‘LARGEST_RECTANGLE’ function in finding the area of the largest rectangle with all 1s is given below.
Algorithm
- Set ‘MAX_AREA’ equal to the 0.
- Initialize ‘PREVIOUS_ROW’ and ‘RESULTANT_ROW’ vectors with values 0 and ‘TOTAL_COLUMNS’ size.
-
For ‘CURRENT_ROW’ from 0 to ‘TOTAL_ROWS’, do:
-
For ‘CURRENT_COLUMN’ from 0 to ‘TOTAL_COLUMNS’, do:
-
If MATRIX[CURRENT_ROW][CURRENT_COLUMN] is not 0, then:
- Set RESULTANT_ROW[CURRENT_COLUMN] = PREVIOUS_ROW[CURRENT_COLUMN] + MATRIX[CURRENT_ROW][CURRENT_COLUMN]
-
Else:
- Set RESULTANT_ROW[CURRENT_COLUMN] = 0.
- Set ‘CURRENT_MAX_AREA’ = LARGEST_RECTANGLE(‘RESULTANT_ROW’ ).
- Set ‘MAX_AREA’ = max(‘MAX_AREA’ , ‘CURRENT_MAX_AREA’ ).
- Set ‘PREVIOUS_ROW’ = ‘RESULTANT_ROW’.
- Return ‘MAX_AREA’.
Program
#include <iostream>
#include <vector>
#include <climits>
#include <stack>
using namespace std;
int largestRectangle(vector<int> &heights)
{
int n = heights.size();
/* The stack holds indexes of heights[] array.
The bars stored in the stack are always in
increasing order of their heights.
*/
stack<int> currentStack;
// Initialize max area.
int maxArea = 0;
// To store the top of the stack.
int topOfStack = 0;
// To store an area with the top bar as the smallest bar.
int areaWithTop = 0;
// Run through all bars of a given histogram.
int i = 0;
while (i < n)
{
/* If this bar is higher than the bar on the top stack,
push it to stack.
*/
if (currentStack.empty() || heights[currentStack.top()] <= heights[i])
{
currentStack.push(i++);
}
else
{
/* Calculate the area with heights[topOfStack]
stack as the smallest bar.
*/
topOfStack = heights[currentStack.top()];
currentStack.pop();
areaWithTop = topOfStack * i;
if (!currentStack.empty())
areaWithTop = topOfStack * (i - currentStack.top() - 1);
maxArea = max(maxArea, areaWithTop);
}
}
/* Now pop the remaining bars from the stack and
calculate the area with every popped bar
as the smallest bar.
*/
while (!currentStack.empty())
{
topOfStack = heights[currentStack.top()];
currentStack.pop();
areaWithTop = topOfStack * i;
if (!currentStack.empty())
areaWithTop = topOfStack * (i - currentStack.top() - 1);
maxArea = max(maxArea, areaWithTop);
}
return maxArea;
}
int maxMatrixArea(vector<vector<int>> &matrix)
{
int totalRows = matrix.size();
int totalColumns = matrix[0].size();
int maxArea = 0;
// Initialize 'PREVIOUS_ROW' and 'RESULTANT_ROW' vectors with values 0 and 'TOTAL_COLUMNS' size.
vector<int> previousRow(totalColumns, 0), resultantRow(totalColumns, 0);
for (int currentRow = 0; currentRow < totalRows; currentRow++)
{
for (int currentColumn = 0; currentColumn < totalColumns; currentColumn++)
{
/* If the current column in 'CURRENT_ROW' is not 0,
add the values of the cells of 'PREVIOUS_ROW' and 'CURRENT_ROW'.
*/
if (matrix[currentRow][currentColumn] != 0)
{
resultantRow[currentColumn] = previousRow[currentColumn] + matrix[currentRow][currentColumn];
}
else
{
/* If the current cell in the 'CURRENT_ROW' is 0,
Assign the value of 0 to the 'RESULTANT_ROW'.
*/
resultantRow[currentColumn] = 0;
}
}
// Find maximum area possible for current resulting histogram.
int currentMaxArea = largestRectangle(resultantRow);
// Comparing the current largest area in the histogram with the largest area so far.
maxArea = max(maxArea, currentMaxArea);
previousRow = resultantRow;
}
return maxArea;
}
int main()
{
// Creating the binary matrix.
int totalRows, TotalColumns;
cout << "Enter Number of Rows in the matrix: ";
cin >> totalRows;
cout << "Enter Number of Columns in the matrix: ";
cin >> TotalColumns;
cout << "Enter the matrix values:\n";
vector<vector<int>> matrix(totalRows, vector<int>(TotalColumns));
for (int i = 0; i < totalRows; i++)
{
for (int j = 0; j < TotalColumns; j++)
{
cin >> matrix[i][j];
}
}
cout << "Area of the largest matrix with all 1s: ";
// Calling the helper function to find the maximum area in the binary matrix.
cout << maxMatrixArea(matrix);
}
Input
Enter Number of Rows in the matrix: 4
Enter Number of Columns in the matrix: 5
Enter the matrix values:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output
Area of the largest matrix with all 1s: 6
Complexity Analysis
Time Complexity: The size of the input vector for the largestReactangle() function is equal to the ‘TOTAL_COLUMNS’. The area of the largest rectangle in a histogram runs in linear time. So, the time complexity for largestReactangle() is O( TOTAL_COLUMNS). For every row from 1 to ‘TOTAL_ROWS’, the area of the largest rectangle in a histogram is calculated. So, the time complexity for the program is O(TOTAL_ROWS x TOTAL_COLUMNS), where ‘TOTAL_ROWS’ and ‘TOTAL_COLUMNS’ represent the total number of rows and columns in the binary matrix respectively.
Space Complexity: Additional space is required to store each row in a stack for the largestReactangle() function. Every row has a ‘TOTAL_COLUMNS’ number of elements. So, the space complexity is O(‘TOTAL_COLUMNS’), where ‘TOTAL_COLUMNS’ represent the total number of columns in the binary matrix.
Check out this problem - Check If A String Is Palindrome
Key Takeaways
Don’t just stop your learning here. There is so much more to learn. Coding Ninjas is here for you to help in your quest for more learning. If you don’t know where to start from, choose one of our guided paths. Listen to your inner voice and head over to Coding Ninjas Studio. You can practice top problems, attempt mock tests, read engaging interview experiences, and much more.
Click here to know about: AngularJS
Happy Coding!
306+ registered