Why Largest Rectangle in Histogram Using Stack in DSA C?

The Big Idea

Discover how a simple stack can save you hours of tedious work finding the biggest rectangle!

The Scenario

Imagine you have a row of buildings with different heights, and you want to find the largest flat area you can cover by choosing some consecutive buildings. Doing this by checking every possible group of buildings one by one is like trying to measure every possible rectangle by hand.

The Problem

Manually checking all groups of buildings is very slow and tiring. It takes a lot of time because you have to look at many combinations, and it is easy to make mistakes counting or comparing heights. This method does not work well when there are many buildings.

The Solution

Using a stack helps keep track of building heights in a smart way. It lets you quickly find the largest rectangle by remembering where taller buildings start and end. This way, you avoid checking every group and find the answer faster and without errors.

Before vs After

✗ Before

int maxArea = 0;
for (int i = 0; i < n; i++) {
  for (int j = i; j < n; j++) {
    int minHeight = heights[i];
    for (int k = i; k <= j; k++) {
      if (heights[k] < minHeight) minHeight = heights[k];
    }
    int area = minHeight * (j - i + 1);
    if (area > maxArea) maxArea = area;
  }
}

✓ After

int largestRectangleArea(int* heights, int n) {
  int maxArea = 0;
  int stack[n];
  int top = -1;
  for (int i = 0; i <= n; i++) {
    int currentHeight = (i == n) ? 0 : heights[i];
    while (top != -1 && currentHeight < heights[stack[top]]) {
      int height = heights[stack[top--]];
      int width = (top == -1) ? i : i - stack[top] - 1;
      int area = height * width;
      if (area > maxArea) maxArea = area;
    }
    stack[++top] = i;
  }
  return maxArea;
}

What It Enables

This method makes it possible to quickly find the largest rectangle in a histogram, even when there are thousands of buildings, without wasting time or making mistakes.

Real Life Example

Architects and city planners can use this to find the biggest flat area in a city skyline for placing billboards or solar panels efficiently.

Key Takeaways

Manual checking of all building groups is slow and error-prone.

Stack helps track building heights smartly for fast calculation.

Enables quick and accurate finding of largest rectangle in histogram.