Largest Histogram Area in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int main(){
    int a[]={2,1,5,6,2,3},n=6,st[100],t=-1,max=0;
    for(int i=0;i<=n;i++){
        int h=(i==n)?0:a[i],idx=i;
        while(t!=-1 && h<a[st[t]]){
            int ht=a[st[t--]];
            int width=(t==-1)?i:i-st[t]-1;
            if(ht*width>max) max=ht*width;
            idx=i;
        }
        st[++t]=idx;
    }
    printf("%d",max);
}

C Output

10

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> a={2,1,5,6,2,3}; stack<int> st; int n=a.size(),mx=0;
    for(int i=0;i<=n;i++){
        int h=(i==n)?0:a[i];
        while(!st.empty() && h<a[st.top()]){
            int ht=a[st.top()]; st.pop();
            int w=st.empty()?i:i-st.top()-1;
            mx=max(mx,ht*w);
        }
        st.push(i);
    }
    cout<<mx;
}

C++ Output

10

JAVA Program

import java.util.*;
class Main{
    public static void main(String[] args){
        int[] a={2,1,5,6,2,3}; Stack<Integer> st=new Stack<>(); int mx=0,n=a.length;
        for(int i=0;i<=n;i++){
            int h=(i==n)?0:a[i];
            while(!st.isEmpty() && h<a[st.peek()]){
                int ht=a[st.pop()];
                int w=st.isEmpty()?i:i-st.peek()-1;
                mx=Math.max(mx,ht*w);
            }
            st.push(i);
        }
        System.out.println(mx);
    }
}

JAVA Output

10

Python Program

a=[2,1,5,6,2,3]
st=[];mx=0
for i in range(len(a)+1):
    h=0 if i==len(a) else a[i]
    while st and h<a[st[-1]]:
        ht=a[st.pop()]
        w=i if not st else i-st[-1]-1
        mx=max(mx,ht*w)
    st.append(i)
print(mx)

Python Output

10

Detailed Explanation

Example

Consider the histogram [2, 1, 5, 6, 2, 3].

The maximum rectangle is covered by the bars of heights 5 and 6 combined, with width 2, resulting in area 5×2=10.

At first it seems that the maximum area will be given by the maximum bar, but actually, joining neighboring bars can result in a much larger rectangle.

Real-Life Analogy

Imagine a city skyline where every building is precisely 1 unit wide, but not all the same height. You want to position the biggest possible billboard against them. The billboard will be rectangular and rub up against the top of buildings without any spaces. Occasionally you'll choose a shorter but broader piece rather than the single highest building, because more breadth can compensate for less height.

Step-by-Step Logic

The secret here is to store indices of bars in non-decreasing height order using a stack.

If we encounter a bar shorter than the top bar in the stack, it implies the taller bar can't go any further — so pop it and find the area with it as the smallest bar in that rectangle.

We continue popping until the present bar is higher than or at the top of the stack.

This guarantees each bar's highest rectangle computed only once.

For each popped bar:

Height = height of that bar

Width = the current index minus index of new top of stack minus one

Update max area if necessary

Finally, we append a 0 height bar to the end to drain out any residual bars from the stack.

Why It Matters

It's a standard stack problem that converts an apparent O(n²) problem into O(n).

It's immediately applicable in problems such as maximal rectangle in binary matrices, image histogram analysis, stock span problems, and even skyline silhouette problems.

Learning Insights

You discover how stacks can be applied to range expansion problems where you need to compute the maximum segment around every element that has some property.

You also observe how to perform end-of-array cleanup using a sentinel value (0 height).

Common Mistakes

Newbies tend to overlook the last cleanup step of adding the 0 height bar. Without this, the stack might still contain unprocessed bars at the end.

Another typical error is applying the improper width formula upon popping and resulting in off-by-one mistakes.

Real-World Applications

Computer vision: determining the largest block among a skyline or segmented image

Histograms in data science: identifying largest contiguous frequency intervals

Building layout optimization: determining the largest possible rectangular billboard or solar panel that can fit on a wall profile

Interview Tips

Interviewers prefer this problem because it challenges stack expertise, meticulous index control, and your power to discern beyond the ignorant brute force.

They can adjust it so that it is applied to 2D binary grids (maximal rectangle), which directly extends from this 1D histogram solution.

SEO-Friendly Closing

Hitting the maximum rectangle in a histogram with a stack is an interview coding and optimization problem must-know algorithm. You can solve it in O(n) time, rather than the naive O(n²) way, by scanning the histogram in one pass with stack-based range expansion. It has broad applications in graphics, computational geometry, and data analysis and is hence one of the most powerful stack-based algorithms in algorithmic problem solving.