LESSON 298 OF 347 · STACK

Largest Rectangle in Histogram in C#: O(n) with a Stack

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.

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.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

1 <= heights.length <= 10⁵
0 <= heights[i] <= 10⁴

STEP 1 OF 18

Guided

Ctrl + Enter to check

C# · STACK

Largest Rectangle In Histogram in C#, explained

Problem overview

A histogram is a row of bars, each of width 1. The array heights holds the height of each bar. The method LargestRectangleArea returns the area of the largest rectangle that fits inside the histogram. The rectangle's sides follow the grid: it covers a run of neighbouring bars and has a height no larger than the shortest of them.

For heights = [2, 1, 5, 6, 2, 3] the answer is 10. The bars of height 5 and 6 are next to each other, so a rectangle of height 5 and width 2 fits over them, with area 10. For [2, 4] the answer is 4: a rectangle of height 4 over the second bar alone, or a rectangle of height 2 over both bars.

The constraints allow up to 100,000 bars, which means checking every pair of start and end positions would be too slow.

Approach: for each bar, find how far it can stretch

Consider the best rectangle, and look at its shortest bar. The rectangle's height equals that bar's height, and it can stretch left and right until it meets a bar that is shorter. So we can try every bar as the limiting one, and for each bar answer one question: how far does a rectangle of this height reach?

For bar i, we need two positions:

left[i]: the index of the nearest bar on the left that is lower than heights[i], or -1 if none exists.
right[i]: the index of the nearest bar on the right that is lower, or n if none exists.

Every bar strictly between those two positions is at least as tall as bar i, so the rectangle is right[i] - left[i] - 1 bars wide. Its area is heights[i] * (right[i] - left[i] - 1), and the answer is the maximum over all bars.

Finding the nearest lower bar is the same job as finding the next greater element, with the comparison flipped. A stack of indices holds the bars that are still waiting, and their heights never decrease from bottom to top. When bar i arrives and is lower than the bar on top, then i is the first lower bar that the top has met, so we record it and pop. Every index is pushed once and popped at most once, so a pass costs O(n). A left-to-right pass fills right, and a right-to-left pass fills left by the same logic.

For [2, 1, 5, 6, 2, 3], the two arrays are right = [1, 6, 4, 4, 6, 6] and left = [-1, -1, 1, 2, 1, 4]. The areas are 2, 6, 10, 6, 8 and 3, and the largest is 10, from the bar of height 5, which spans positions 2 and 3.

Step by step

Store the bar count as n.
Create left, an int array of size n filled with -1, as if a bar of height 0 stood just before the first one.
Create right, filled with n, as if a bar of height 0 stood just after the last one.
Create an empty Stack<int> that will hold indices.
Scan from left to right with i from 0 to n - 1.
Call the helper RemoveAndUpdate(heights, stack, right, i). Scanning rightwards, the first lower bar an index meets is its nearest lower bar on the right.
Clear the stack. The indices left on it have no lower bar to their right, and keep n. The second pass needs an empty stack.
Scan from right to left, with i from n - 1 down to 0, using the condition i >= 0 so index 0 is included.
Call the helper with left. Scanning leftwards, the same logic finds each bar's nearest lower bar on the left.
Start answer at 0. Areas are never negative.
Loop over every bar and treat it as the limiting height.
Update the maximum with Math.Max(answer, heights[i] * (right[i] - left[i] - 1)). The subtraction of 1 excludes the two lower bars themselves.
Return answer.
Write the helper. It is a public void method with the parameters int[] heights, Stack<int> stack, int[] arr and int i. The array arr is whichever of left or right the caller passes.
Pop the taller bars. A while loop runs while the stack is not empty and heights[i] is less than the height at the top index.
Record and pop. Set arr[stack.Peek()] = i, then call stack.Pop().
Push i after the loop, so it waits for its own lower bar. Only strictly taller bars are popped, so bars of the same height stay.

The solution in C#

class Solution {
    public void RemoveAndUpdate(int[] heights, Stack<int> stack, int[] arr, int i) {
        while (stack.Count > 0 && heights[i] < heights[ stack.Peek() ]) {
            arr[ stack.Peek() ] = i;
            stack.Pop();
        }
        stack.Push(i);
    }

    public int LargestRectangleArea(int[] heights) {
        int n = heights.Length;
        int[] left = new int[n];
        Array.Fill(left, -1);
        int[] right = new int[n];
        Array.Fill(right, n);

        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < n; i++) {
            RemoveAndUpdate(heights, stack, right, i);
        }

        stack.Clear();
        for (int i = n - 1; i >= 0; i--) {
            RemoveAndUpdate(heights, stack, left, i);
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer = Math.Max(answer, heights[i] * (right[i] - left[i] - 1));
        }

        return answer;
    }
}

Some C# details to notice:

Reference types are shared. Arrays and Stack<int> objects are reference types. The helper receives the caller's own stack and array, not copies, so its writes to arr and its pushes and pops are visible to the caller. That is why the helper can return void.
Calling the helper. Both methods are instance methods of Solution, so RemoveAndUpdate(...) is called by name from inside the class.
Short-circuit evaluation. In the helper's condition, stack.Count > 0 comes first, so stack.Peek() is never called on an empty stack.
Array.Fill and Clear. A new int array holds zeros, so the fills with -1 and n are necessary. stack.Clear() empties the same stack object for the second pass.
Two loops, two is. Each for loop declares its own i, and it exists only inside that loop, so the same name can be reused.
Integer range. With heights up to 10,000 and up to 100,000 bars, the largest possible area is 1,000,000,000, which fits in an int (the maximum is about 2.1 billion).

Complexity

Time: O(n). Each of the two passes pushes every index once and pops it at most once, so each pass is linear. The final loop is linear too, so the total is O(n).

Space: O(n). The arrays left and right and the stack each hold up to n numbers.

Edge cases and common mistakes

Equal heights. For [3, 3, 3] the answer is 9. The helper pops only strictly taller bars, so equal bars never limit each other. Every bar then has left = -1 and right = 3, and a width of 3.
A zero-height bar. In [2, 0, 2] the zero splits the histogram, and the answer is 2. The zero itself gives area 0, but its width is the whole row.
A single bar. For [7] the answer is 7, with left = -1 and right = 1.
Sorted heights. For [5, 4, 3, 2, 1] the answer is 9, from height 3 and width 3.
Forgetting the sentinel values. Leaving left and right at 0 would shrink the widths of bars that have no lower neighbour.
Using the wrong width. The width is right[i] - left[i] - 1. Without the - 1, the two lower bars at the ends would be counted inside the rectangle.
Skipping stack.Clear(). Leftover indices from the first pass would be compared against the wrong bars in the second pass.

Testing

heights = [2, 1, 5, 6, 2, 3] gives 10.
heights = [2, 4] gives 4.
heights = [3, 3, 3] gives 9.
heights = [2, 0, 2] gives 2.
heights = [5, 4, 3, 2, 1] gives 9.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free