Editorial - PREP22 - Largest Rectangle in Histogram

editorial
1

Explanation

This problem revolves around finding the largest rectangular area in a histogram. The histogram is represented by an array where each element signifies the height of the bar and the width is assumed to be 1 unit for all bars.

To solve this problem, we can use a stack to keep track of the bars that are not yet part of the maximum rectangle. We traverse the list of bar heights and for each height h, we do the following:

  1. If the stack is empty or h is greater than the height of the bar at the stack’s top, push the current index onto the stack, indicating that this bar has the potential to be part of a larger rectangle.
  2. If h is less than or equal to the height of the bar at the stack’s top, it means that we cannot extend the rectangle that includes the bar at the stack’s top any further to the right. Hence, we pop the stack, calculate the area of the rectangle that includes the popped bar as the shortest bar, and update the maximum area if necessary. The width of the rectangle is the difference between the current index and the index at the new top of the stack minus one (as we want the number of bars including the current and all bars on the left till the one at the current top).
  3. After we finish processing each height, there might still be indices left in the stack. These correspond to bars that could potentially extend all the way to the end of the histogram. We process them similarly as in step 2, only now the width extends to the end of the histogram.

C++ Solution

#include <iostream>
#include <stack>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--){
	    int N;
	    cin>>N;
	    long A[N];
	    for (int i=0; i<N; i++)
	        cin>>A[i];
	    stack<int> S;
	    S.push(-1);
	    long res = 0;
	    for (int i=0; i<N; i++) {
	        int x = A[i];
	        while (S.top() != -1 && A[S.top()]>=x) {
	            int y = S.top();
	            S.pop();
	            res = max(res, A[y]*(i-1-S.top()));
	        }
	        S.push(i);
	    }
	        while (S.top() != -1) {
	            int y = S.top();
	            S.pop();
	            res = max(res, A[y]*(N-1-S.top()));
	        }
	    cout<<res<<endl;
	}
	return 0;
}

Python Solutions

t = int(input())
for _ in range(t):
    N = int(input())
    A = list(map(int, input().split()))
    S = [-1]
    res = 0
    for i in range(N):
        x = A[i]
        while S[-1] != -1 and A[S[-1]] >= x:
            y = S.pop()
            res = max(res, A[y] * (i - 1 - S[-1]))
        S.append(i)
    while S[-1] != -1:
        y = S.pop()
        res = max(res, A[y] * (N - 1 - S[-1]))
    print(res)

Java Solution

import java.util.Scanner;
import java.util.Stack;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for (int k = 0; k < t; k++) {
            int N = scanner.nextInt();
            long[] A = new long[N];
            for (int i = 0; i < N; i++)
                A[i] = scanner.nextLong();

            Stack<Integer> S = new Stack<>();
            S.push(-1);
            long res = 0;
            for (int i = 0; i < N; i++) {
                int x = (int) A[i];
                while (S.peek() != -1 && A[S.peek()] >= x) {
                    int y = S.pop();
                    res = Math.max(res, A[y] * (i - 1 - S.peek()));
                }
                S.push(i);
            }
            while (S.peek() != -1) {
                int y = S.pop();
                res = Math.max(res, A[y] * (N - 1 - S.peek()));
            }
            System.out.println(res);
        }
    }
}