Maximum Histogram Area — Problem Statement & Solution Guide

StackHardLargest Rectangle Histogram

TimeO(N)

SpaceO(N)

Problem Description

You are provided with an array of non-negative integers, where each integer represents the height of a vertical bar in a histogram. The bars are adjacent to each other and have a uniform width of 1 unit. Your task is to determine the maximum possible area of a rectangle that can be formed within the histogram. The rectangle must be aligned with the x-axis, and its height is constrained by the shortest bar in the contiguous segment it spans. Specifically, for any contiguous subarray of bars, the area of the rectangle formed is the product of the minimum height in that subarray and the length of the subarray. Return the maximum such area across all possible contiguous subarrays.

Input: An array heights of integers, where heights[i] denotes the height of the i-th bar.

Output: A single integer representing the maximum area of the rectangle that can be formed within the histogram.

DSA Pattern Breakdown

"Maximum Histogram Area"

hard

WHY DOES IT MATTER?

The monotonic stack pattern is essential because it transforms a seemingly quadratic problem into a linear one by exploiting order relationships. Mastery of this pattern unlocks efficient solutions for a family of problems involving next‑greater/next‑smaller element queries, which appear frequently in coding interviews and production code.

OPTIMIZATION CHALLENGE

The key insight is that each bar's maximal rectangle is bounded by the first smaller bar on its left and right. By maintaining a stack of increasing heights, we can discover these boundaries on‑the‑fly, ensuring each element is processed only twice (once when pushed, once when popped).

REAL-WORLD CONNECTION

Think of a load‑balancing system where each server's capacity is a bar height; the algorithm quickly finds the largest contiguous group of servers that can handle a uniform workload without exceeding the weakest server, analogous to finding the maximal rectangle in a histogram.

During an interview, push the sentinel trick early, walk through a small example on the whiteboard, and explicitly state that each index is pushed and popped at most once—this demonstrates both correctness and optimality.

COMPLEXITY AT A GLANCE

⏱ Time:O(N)

💾 Space:O(N)

Core Theory — Why This Approach?

The "Maximum Histogram Area" problem is a classic example of using a monotonic stack to achieve linear time complexity. A naive solution would examine every possible pair of bars, compute the minimum height between them, and multiply by the width, resulting in O(N^2) time which quickly becomes infeasible for large N (N can be up to 10^5 or more in interview settings). The optimal paradigm leverages the observation that for each bar we can determine the nearest smaller bar to its left and right; these boundaries define the maximal width where the current bar remains the limiting height. By scanning the histogram once while maintaining a stack of indices with increasing heights, we can pop when we encounter a lower height, instantly calculate the area for the popped bar using the current index as the right boundary and the new stack top as the left boundary. This stack‑based algorithm guarantees O(N) time and O(N) auxiliary space, making it the de‑facto solution for the problem.

Interview Questions on This Problem

Q1How does the monotonic stack help compute the largest rectangle in a histogram in O(N) time?

The stack stores indices of bars in increasing height order. When a lower bar appears, we pop higher bars, each pop gives the height of the popped bar and the width as the distance between the current index (right boundary) and the new stack top (left boundary). This immediate area calculation avoids re‑scanning, ensuring each bar is pushed and popped at most once, yielding linear time.

Q2Can you modify the algorithm to handle histograms where bars have varying widths?

Yes. Instead of assuming unit width, store cumulative widths or prefix sums alongside indices. When popping a bar, compute width as the difference between the cumulative width at the current position and the cumulative width at the new stack top, then multiply by the popped height. The stack logic remains unchanged.

Q3Why might adding a sentinel zero height at the end of the array simplify implementation?

Appending a zero forces the stack to empty at the end of the scan, guaranteeing that the area for every bar is evaluated. It eliminates the need for a separate post‑processing loop, reduces edge‑case code, and keeps the algorithm clean and bug‑free.

Examples

Example 1

Input

heights = [2, 1, 5, 6, 2, 3]

Output

Explanation: Consider the subarray [5, 6]. The minimum height is 5, and the width is 2, yielding an area of 10. Other candidates: [2, 1, 5, 6, 2, 3] has min 1 and width 6 (area 6); [5, 6, 2, 3] has min 2 and width 4 (area 8); [6] has area 6. The maximum area is 10.

Example 2

Input

heights = [6, 2, 5, 4, 5, 1, 6]

Output

Explanation: Consider the subarray [5, 4, 5]. The minimum height is 4, and the width is 3, yielding an area of 12. Other candidates: [6] has area 6; [2, 5, 4, 5, 1, 6] has min 1 and width 6 (area 6); [5, 4, 5, 1, 6] has min 1 and width 5 (area 5). The maximum area is 12.

Example 3

Input

heights = [1, 1, 1, 1, 1]

Output

Explanation: All bars have height 1. The entire array forms a rectangle of height 1 and width 5, yielding an area of 5. Any smaller subarray yields a smaller area. Thus, the maximum area is 5.

Example 4

Input

heights = [3, 3, 3, 3]

Output

Explanation: All bars have height 3. The entire array forms a rectangle of height 3 and width 4, yielding an area of 12. This is the maximum possible area since all bars are of equal height.

Constraints

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^9
The answer is guaranteed to fit within a 64-bit integer.

Optimal Approach & Strategy

Use a monotonic increasing stack to find the nearest smaller bar on both sides for each index, calculating area on the fly; this runs in O(N) time with O(N) extra space.

Brute Force Approach

Iterate over all possible left and right boundaries, compute the minimum height in that range, and calculate area; this requires O(N^2) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N)

function solution(nums) {
      let stack = [];
      let maxArea = 0;
      for (let i = 0; i < nums.length; i++) {
         while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {
            let height = nums[stack.pop()];
            let width = stack.length > 0 ? i - stack[stack.length - 1] - 1 : i;
            maxArea = Math.max(maxArea, height * width);
         }
         stack.push(i);
      }
      while (stack.length > 0) {
         let height = nums[stack.pop()];
         let width = stack.length > 0 ? nums.length - 1 - stack[stack.length - 1] : nums.length - 1;
         maxArea = Math.max(maxArea, height * width);
      }
      return maxArea;
   }

class Solution {
   public:
      int solution(vector<int>& nums) {
         vector<int> stack;
         int maxArea = 0;
         for (int i = 0; i < nums.size(); i++) {
            while (!stack.empty() && nums[stack.back()] > nums[i]) {
               int height = nums[stack.back()];
               stack.pop_back();
               int width = stack.empty() ? i : i - stack.back() - 1;
               maxArea = max(maxArea, height * width);
            }
            stack.push_back(i);
         }
         while (!stack.empty()) {
            int height = nums[stack.back()];
            stack.pop_back();
            int width = stack.empty() ? nums.size() - 1 : nums.size() - 1 - stack.back();
            maxArea = max(maxArea, height * width);
         }
         return maxArea;
      }
   };

class Solution {
      public int solution(int[] nums) {
         int[] stack = new int[nums.length];
         int top = -1;
         int maxArea = 0;
         for (int i = 0; i < nums.length; i++) {
            while (top > -1 && nums[stack[top]] > nums[i]) {
               int height = nums[stack[top--]];
               int width = top > -1 ? i - stack[top] - 1 : i;
               maxArea = Math.max(maxArea, height * width);
            }
            stack[++top] = i;
         }
         while (top > -1) {
            int height = nums[stack[top--]];
            int width = top > -1 ? nums.length - 1 - stack[top] : nums.length - 1;
            maxArea = Math.max(maxArea, height * width);
         }
         return maxArea;
      }
   }

def solution(nums):
      stack = []
      maxArea = 0
      for i in range(len(nums)):
         while stack and nums[stack[-1]] > nums[i]:
            height = nums[stack.pop()]
            width = stack[-1] + 1 if stack else i
            maxArea = max(maxArea, height * width)
         stack.append(i)
      while stack:
         height = nums[stack.pop()]
         width = len(nums) - 1 - stack[-1] if stack else len(nums) - 1
         maxArea = max(maxArea, height * width)
      return maxArea

function solution(nums) {
      let stack = [];
      let maxArea = 0;
      for (let i = 0; i < nums.length; i++) {
         while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {
            let height = nums[stack.pop()];
            let width = stack.length > 0 ? i - stack[stack.length - 1] - 1 : i;
            maxArea = Math.max(maxArea, height * width);
         }
         stack.push(i);
      }
      while (stack.length > 0) {
         let height = nums[stack.pop()];
         let width = stack.length > 0 ? nums.length - 1 - stack[stack.length - 1] : nums.length - 1;
         maxArea = Math.max(maxArea, height * width);
      }
      return maxArea;
   }

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Maximum Histogram Area Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Stack

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Maximum Histogram Area — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor