Problem

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Examples

Example 1:

Input:
heights = [2,1,5,6,2,3]
Output:
 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

This is the largest rectangle: Example 2:

Input:
heights = [2,4]
Output:
 4
Explnation - either 1*4 OR 2*2 rectangle

Solution

Method 1 - Brute Force

A simple solution is to one by one consider all bars as starting points and calculate area of all rectangles starting with every bar. Finally return maximum of all possible areas.

Time complexity of this solution would be O(n^2).

public int largestRectanglularAreaInHistogram(int[] hist) {
	int maxArea = 0;

	// Iterate through the histogram.
	for (int i = 0; i<hist.length; ++i) {
		int h = hist[i];

		maxArea = Math.max(maxArea, h);

		for (int j = i - 1; j >= 0; --j) {
			final int w = (i - j + 1);

			h = Math.min(h, hist[j]);

			maxArea = Math.max(maxArea, h * w);
		}
	}

	return maxArea;
}

For example, given hist=[2, 3, 1, 4, 5, 4, 2], the iteration in visual looks like:

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Finding Nearest Smaller to Left and Right

We have seen Next Greater Element 1 already. There we used stack to do so. But before that let us understand why we need NSL and NSR. They are:

  • Next or Nearest smaller element to left (NSL)
  • Next or Nearest smaller element to right (NSR)

Key Observation 1

[!NOTE] Key Observation Whenever we are making a largest rectangle, atleast one bar or heights[i] is included in full.

Lets look at some examples

Examples
Example 1

Largest rectangle includes heights[1] in full. Largest rectange = 6 in area.

Example 2

Largest rectangle includes heights[3] and heights[4] in full. Largest rectange = 12 in area.

Key Observation 2

Whenever we including a full bar in rectangle, we need to look at the left and right of it to make a rectangle.

What is the limit to making such a rectangle?

  • The limit is the height of left and right bars.
  • All the bars on the left or right of the current bar (or heights[i]) should be either less than or equal to the current bar, to be included in current rectangle.

[!NOTE] Observation 2 For current bar, we need NSR and NSL to make a current rectangle with height of that bar

That is why we need NSR and NSL. Now the algo.

Examples

Consider the heights:

Lets try to make the rectangle at index 4, then this the rectangle we can form:

How did we form this rectangle:

  • We need to find nearest left bar whose height <= current bar, else 0
  • We need to find the nearest right bar whose height <= current bar, else n-1 (n = length of 0-indexed array)

Formula:

height = heights[i]
width = NSR(i) - NSL(i) + 1
area = height * width
maxArea = max(maxArea, area)

Algo

  • calclulate NSL (Nearest smallest to Left) for all elements, let’s call that left
  • calclulate NSR (Nearest smallest to Right) for all elements, let’s call that right
  • calculate width as right[i] - left[i] - 1
  • find area as heights[i] * width[i]
  • return max area
Algorithm to Find NSL and NSR

To find NSL, we jave to use monotonic stack. We have solved it for NGL here - NGL - Nearest Greater Element to Left of every element.

We have solved NGR (nearest greater on right): NGR - Nearest Greater Element to Right of every element

Here are for smaller versions:

Code

public int largestRectangleArea(int[] arr) {
	int n = arr.length;

	int[] l = NSL(arr); //nearest smaller to left
	int[] r = NSR(arr); //nearest smaller to right

	int max = Integer.MIN_VALUE;
	for (int i = 0; i<n; i++) {
		int area = arr[i] * (r[i] - l[i] + 1);
		max = Math.max(max, area);
	}

	return max;
}

private int[] NSL(int[] arr) {
	int n = arr.length;
	int[] left = new int[n];

	Stack<Integer> stack = new Stack<>();
	for (int i = 0; i<n; i++) {
		if (stack.isEmpty()) {
			left[i] = 0;
		} else {
			while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
				stack.pop();
			}
			left[i] = stack.isEmpty() ? 0 : stack.peek() + 1;
		}
		stack.push(i);
	}

	return left;
}

private int[] NSR(int[] arr) {
	int n = arr.length;
	int[] right = new int[n];

	Stack<Integer> stack = new Stack<>();
	for (int i = arr.length - 1; i >= 0; i--) {
		if (stack.isEmpty()) {
			right[i] = n - 1;
		} else {
			while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
				stack.pop();
			}
			right[i] = stack.isEmpty() ? n - 1 : stack.peek() - 1;

		}
		stack.push(i);
	}
	return right;
}

Method 3 - Using One Monotonic Increasing Stack, O(n)

In the naive approach, there are some redundant iterations that we obviously could skip. For example: Given i=3 and j=2, the height is 1, and we already know that the area from i=2 to 0 is 3×1 because we previously traverse it when i=2.

Why Stack?

At each step we need the information of previously seen “candidate” bars - bars which give us hope. These are the bars of increasing heights. And since they’ll need to be put in the order of their occurence, stack should come to your mind.

Lets take the example [2, 1, 5, 6, 2, 3]

Lets start by adding a bar of height 0 as starting point to the stack. This has no inherent meaning, and is just done to make the solution more elegant.

The first bar we see is the bar at position 0 of height 2. It is definitely as “candidate bar” as it gives us hope of finding a larger rectangle, so we just add it to the stack.

The next one we see is the bar at position 1 with height 1. At this point, we look at the stack and see that the “candidate bar” at the top of the stack is of height 2, and because of this 1, we definitely can’t do a rectangle of height 2 now, so the only natural thing to do at this point is to pop it out of the stack, and see what area it could have given us.

This bar started at position -1 (which is now at the top of the stack), and ended at position 1, thus giving a width of 1-(-1)-1 = 1, and height of 2 hence we update our maxArea to 2, and now check the next element on top of the stack (to see if that could be popped out as well) - and since it is 0 < 1, it can’t be popped out. Thus,

height = stack.pop()
width = i - stack[-1] - 1
maxArea = max(maxArea, width*height)

Algorithm

Following is the complete algorithm.

  1. In the stack, we store height index which heights are ascending order. (Note we are adding index and not the array values)
  2. a) If stack is empty or hist[i] is higher than the bar at top of stack, then push i to stack. b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the left index is previous (previous to tp) item in stack and right index is i (current index).
  3. If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.
Dry Running Above Algo

Consider the heights array: [2,1,5,6,2,3] For example, When we proceed to the index with height 2. We push it to stack. Then we see heights[1] as 1, which is less than 2. Hence we have to deal with what is in stack. So, we pop out 2 and calculate area.

Then we push 1, 5 and 6 value indices in stack.

The stack stores 1, 5, 6, then we pop the elements one by one.

After we pop the element out, we compute the area which height is this pop height.

For height with 6, the area is (i - stack.peek() - 1) * 6(i is current index, index of height 2; stack.peek() is index of height 5)

Code

Java
public int largestRectangleArea(int[] heights) {
	int n = heights.length;
	Stack<Integer> stack = new Stack();
	int maxArea = 0;
	for (int i = 0; i<= n; i++) {
		int h = i == n ? 0 : heights[i];
		
		while (!stack.isEmpty() && h<heights[stack.peek()]) {
			int curHeight = heights[stack.pop()];
			int curWidth = stack.isEmpty() ? i : i - stack.peek() - 1;
			int area = curHeight * curWidth;
			maxArea = Math.max(maxArea, area);
		}
		stack.push(i);
	}
	return maxArea;
}

Complexity

  • ⏰ Time complexity: O(n) (O(2n) = O(n)`)
  • 🧺 Space complexity: O(n), (size of the stack in worst case)
How to Understand i - 1 - stack.peek()

#TODO cleanup

Why We Have Equality with N in for Loop Condition?

Why are we having loop like:

for (int i = 0; i<= n; i++) {
}

instead of :

for (int i = 0; i< n; i++) {
}

The reason is very simple, it saves us from processing the remaining stack when the loop is over. Here is the code when we don’t use equality in condition:

public int largestRectangleArea(int[] heights) {
	Stack<Integer> stack = new Stack<>();
	int result = 0;
	int len = height.length;
	for (int i = 0; i < height.length; ) {
		if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
			stack.push(i);
			i++;
		} else {
			result = Math.max(result, calculateArea(height, stack, i));
		}
	}
	while (!stack.isEmpty()) {
		result = Math.max(result, calculateArea(height, stack, len));
	}
	return result;
}

private int calculateArea(int[] height, Stack<Integer> stack, int i) {
	int index = stack.pop();
	int h = heights[index];
	int w = stack.isEmpty() ? i : i - stack.peek() - 1;
	return h * w;
}

Code 2 - WIth Left and Right Boundary 🏆

So, whenever value is more than stack’s peek, we will increase our right boundary. Whenver we have a smaller value, we need to process elements in stack, and get the left boundary. Area = current height * (right boundary - left boundary + 1)

public int largestRectangleArea(int[] heights) {
	int n = heights.length;
	int maxArea = 0;
	Stack<Integer> stack = new Stack<>();
	for (int i = 0; i <= n;) {
		int h = (i == n ? 0 : heights[i]);
		if (stack.isEmpty() || h >= heights[stack.peek()]) {
			stack.push(i);
			// move right boundary
			i++;
		}else {
			// we dont increase i, 
			// as we are not processing ith height 
			// but stack height
			int curHeight = heights[stack.pop()];
			int rightBoundary = i - 1; // prev element
			int leftBoundary = stack.isEmpty() ? 0 : stack.peek() + 1;
			int width = rightBoundary - leftBoundary + 1;
			maxArea = Math.max(maxArea, (curHeight * width));
		}
	}
	return maxArea;
}

Method 4 - Divide and Conquer (NlgN)

The concept revolves around pinpointing the array’s smallest element. Once identified, the largest possible area is derived from one of the following: a) The largest area to the left of the smallest value (excluding the minimum itself) b) The largest area to the right of the smallest value (excluding the minimum too) c) The product of the bar count and the minimum value itself.

Calculating areas on both sides of the smallest bar utilizes a recursive strategy. Should a linear search be deployed to locate the minimum, the algorithm may degrade to O(n^2) complexity in the worst scenario. This mirrors the least efficient outcome of Quick Sort, where one side retains n-1 elements and the other none.

To determine the minimum more adeptly, leverage the [[Range Minimum Query RMQ Problem|Range Minimum Query via Segment Tree]]. Erect a segment tree from the histogram’s heights, and subsequent range minimum searches will run in O(Logn). Hence, the algorithm’s total complexity amalgamates the time to construct the segment tree, O(n), with the recursive search for maximum area, denoted T(n), as follows:

T(n) = O(Logn) + T(n-1)

Code

Java
class Solution {
    public int largestRectangleArea(int[] heights) {
        SegTree segTree = new SegTree(heights);
        return largestRectangleArea(heights, 0, heights.length-1, segTree);
    }

    private int largestRectangleArea(int[] heights, int startIdx, int endIdx, SegTree segTree){
        if(startIdx > endIdx)
            return -1;

        int minHeightIdx = segTree.getMinIdx(startIdx, endIdx, heights);
        int minHeight = heights[minHeightIdx];
        int maxArea = 0;
        int distance = endIdx - startIdx + 1;

        maxArea = Math.max(maxArea, minHeight * distance);
        maxArea = Math.max(maxArea, largestRectangleArea(heights, startIdx, minHeightIdx-1, segTree));
        maxArea = Math.max(maxArea, largestRectangleArea(heights, minHeightIdx+1, endIdx, segTree));
        return maxArea;
    }
}

class SegTree{
    SegNode root;
    SegTree(int[] heights){
        root = new SegNode(0, heights.length-1, heights);
    }

    public int getMinIdx(int startIdx, int endIdx, int[] heights){
        return root.getMinNode(startIdx, endIdx, heights);
    }
}

class SegNode{
    int minVal;
    int minIdx;

    int startIdx;
    int endIdx;

    SegNode left;
    SegNode right;

    SegNode( int startIdx, int endIdx, int[] heights){
        this.startIdx = startIdx;
        this.endIdx = endIdx;

        if(startIdx == endIdx){
            minVal = heights[startIdx];
            minIdx = startIdx;
        }
        else{
            int mid = (endIdx-startIdx)/2 + startIdx;
            left = new SegNode(startIdx, mid, heights);
            right = new SegNode(mid+1, endIdx, heights);

            if(left.minVal < right.minVal){
                minVal = left.minVal;
                minIdx = left.minIdx;
            }
            else{
                minVal = right.minVal;
                minIdx = right.minIdx;
            }
        }
    }

    public int getMinNode(int startIdx, int endIdx, int[] heights){
        if(this.startIdx >= startIdx && this.endIdx <= endIdx){
            return minIdx;
        }

        // If range is completely out of bound, return -1
        if(startIdx > this.endIdx || endIdx < this.startIdx){
            return -1;
        }
        
        int leftMinIdx = left.getMinNode(startIdx, endIdx, heights);
        int rightMinIdx = right.getMinNode(startIdx, endIdx, heights);
        
        if(leftMinIdx != -1 && rightMinIdx != -1){
            if(heights[leftMinIdx] < heights[rightMinIdx])
                return leftMinIdx;
            return rightMinIdx;
        }
        if(leftMinIdx != -1)
            return leftMinIdx;
        return rightMinIdx;
    }

}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)