84. Largest Rectangle In Histogram - Explanation

Description

You are given an array of integers heights where heights[i] represents the height of a bar. The width of each bar is 1.

Return the area of the largest rectangle that can be formed among the bars.

Note: This chart is known as a histogram.

Example 1:

Input: heights = [7,1,7,2,2,4]

Output: 8

Example 2:

Input: heights = [1,3,7]

Output: 7

Constraints:

1 <= heights.length <= 1000.
0 <= heights[i] <= 1000

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Hint 1

A rectangle has a height and a width. Can you visualize how rectangles are formed in the given input? Considering one bar at a time might help. We can try to form rectangles by going through every bar and current bar's height will be the height of the rectangle. How can you determine the width of the rectangle for the current bar being the height of the rectangle? Extending the current bar to the left and right might help determine the rectangle's width.

Hint 2

For a bar with height h, try extending it to the left and right. We can see that we can't extend further when we encounter a bar with a smaller height than h. The width will be the number of bars within this extended range. A brute force solution would be to go through every bar and find the area of the rectangle it can form by extending towards the left and right. This would be an O(n^2) solution. Can you think of a better way? Maybe precomputing the left and right boundaries might be helpful.

Hint 3

The left and right boundaries are the positions up to which we can extend the bar at index i. The area of the rectangle will be height[i] * (right - left + 1), which is the general formula for height * width. These boundaries are determined by the first smaller bars encountered to the left and right of the current bar. How can we find the left and right boundaries now? Maybe a data structure is helpful.

Hint 4

We can use a stack with a monotonically strictly increasing nature, but instead of storing values, we store indices in the stack and perform operations based on the values at those indices. The top of the stack will represent the smaller bar that we encounter while extending the current bar. To find the left and right boundaries, we perform this algorithm from left to right and vice versa, storing the boundaries. Then, we iterate through the array to find the area for each bar and return the maximum area we get.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Monotonic Stack - Using a stack to efficiently track elements in increasing/decreasing order
Next Smaller Element Pattern - Finding the nearest smaller element on left and right for each position
Divide and Conquer - Breaking problems into subproblems based on minimum elements (for segment tree approach)
Array Traversal - Iterating through arrays while maintaining state

1. Brute Force

Intuition

For every bar, we try to treat it as the shortest bar in the rectangle.
To find how wide this rectangle can extend, we look left and right until we hit a bar shorter than the current one.
The width between these two boundaries gives the largest rectangle where this bar is the limiting height.
We repeat this for every bar and keep track of the maximum rectangle found.

Algorithm

Let maxArea store the largest rectangle found.
For each index i:
- Let height be the height of the current bar.
- Expand to the right until you find a bar shorter than height.
- Expand to the left while bars are not shorter than height.
- Compute the width between the boundaries.
- Update maxArea with height * width.
Return maxArea.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        maxArea = 0

        for i in range(n):
            height = heights[i]

            rightMost = i + 1
            while rightMost < n and heights[rightMost] >= height:
                rightMost += 1

            leftMost = i
            while leftMost >= 0 and heights[leftMost] >= height:
                leftMost -= 1

            rightMost -= 1
            leftMost += 1
            maxArea = max(maxArea, height * (rightMost - leftMost + 1))
        return maxArea

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;

        for (int i = 0; i < n; i++) {
            int height = heights[i];

            int rightMost = i + 1;
            while (rightMost < n && heights[rightMost] >= height) {
                rightMost++;
            }

            int leftMost = i;
            while (leftMost >= 0 && heights[leftMost] >= height) {
                leftMost--;
            }

            rightMost--;
            leftMost++;
            maxArea = Math.max(maxArea, height * (rightMost - leftMost + 1));
        }
        return maxArea;
    }
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int maxArea = 0;

        for (int i = 0; i < n; i++) {
            int height = heights[i];

            int rightMost = i + 1;
            while (rightMost < n && heights[rightMost] >= height) {
                rightMost++;
            }

            int leftMost = i;
            while (leftMost >= 0 && heights[leftMost] >= height) {
                leftMost--;
            }

            rightMost--;
            leftMost++;
            maxArea = max(maxArea, height * (rightMost - leftMost + 1));
        }
        return maxArea;
    }
};

class Solution {
    /**
     * @param {number[]} heights
     * @return {number}
     */
    largestRectangleArea(heights) {
        const n = heights.length;
        let maxArea = 0;

        for (let i = 0; i < n; i++) {
            let height = heights[i];

            let rightMost = i + 1;
            while (rightMost < n && heights[rightMost] >= height) {
                rightMost++;
            }

            let leftMost = i;
            while (leftMost >= 0 && heights[leftMost] >= height) {
                leftMost--;
            }

            rightMost--;
            leftMost++;
            maxArea = Math.max(maxArea, height * (rightMost - leftMost + 1));
        }
        return maxArea;
    }
}

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int n = heights.Length;
        int maxArea = 0;

        for (int i = 0; i < n; i++) {
            int height = heights[i];

            int rightMost = i + 1;
            while (rightMost < n && heights[rightMost] >= height) {
                rightMost++;
            }

            int leftMost = i;
            while (leftMost >= 0 && heights[leftMost] >= height) {
                leftMost--;
            }

            rightMost--;
            leftMost++;
            maxArea = Math.Max(maxArea, height * (rightMost - leftMost + 1));
        }
        return maxArea;
    }
}

func largestRectangleArea(heights []int) int {
    n := len(heights)
    maxArea := 0

    for i := 0; i < n; i++ {
        height := heights[i]

        rightMost := i + 1
        for rightMost < n && heights[rightMost] >= height {
            rightMost++
        }

        leftMost := i
        for leftMost >= 0 && heights[leftMost] >= height {
            leftMost--
        }

        rightMost--
        leftMost++

        area := height * (rightMost - leftMost + 1)
        if area > maxArea {
            maxArea = area
        }
    }

    return maxArea
}

class Solution {
    fun largestRectangleArea(heights: IntArray): Int {
        val n = heights.size
        var maxArea = 0

        for (i in 0 until n) {
            val height = heights[i]

            var rightMost = i + 1
            while (rightMost < n && heights[rightMost] >= height) {
                rightMost++
            }

            var leftMost = i
            while (leftMost >= 0 && heights[leftMost] >= height) {
                leftMost--
            }

            rightMost--
            leftMost++

            maxArea = maxOf(maxArea, height * (rightMost - leftMost + 1))
        }

        return maxArea
    }
}

class Solution {
    func largestRectangleArea(_ heights: [Int]) -> Int {
        let n = heights.count
        var maxArea = 0

        for i in 0..<n {
            let height = heights[i]

            var rightMost = i + 1
            while rightMost < n && heights[rightMost] >= height {
                rightMost += 1
            }

            var leftMost = i
            while leftMost >= 0 && heights[leftMost] >= height {
                leftMost -= 1
            }

            rightMost -= 1
            leftMost += 1
            maxArea = max(maxArea, height * (rightMost - leftMost + 1))
        }

        return maxArea
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Divide And Conquer (Segment Tree)

Intuition

A large rectangle in the histogram must have some bar as its shortest bar.
If we know the index of the minimum height bar in any range, then:

The largest rectangle that uses that bar as the limiting height spans the entire range.
Anything larger must lie entirely on the left or entirely on the right of that bar.

So we can solve the problem with a divide and conquer idea:

In a given range [L, R], find the index of the smallest bar.
Compute:
- The area using this bar across the whole range.
- The best area entirely in [L, minIndex - 1].
- The best area entirely in [minIndex + 1, R].
The answer for [L, R] is the maximum of those three.

To find the index of the minimum height quickly for any range, we use a segment tree built on heights. It supports “min index in range” queries in O(log n) time, which makes the whole divide-and-conquer efficient.

Algorithm

Build a segment tree over the heights array:
- Each node stores the index of the minimum height in its segment.
Define a recursive function solve(L, R):
- If L > R, return 0.
- If L == R, return heights[L] (only one bar).
- Use the segment tree to find minIndex = index of the smallest bar in [L, R].
- Compute:
  - area_with_min = heights[minIndex] * (R - L + 1)
  - area_left = solve(L, minIndex - 1)
  - area_right = solve(minIndex + 1, R)
- Return max(area_with_min, area_left, area_right).
The final answer is solve(0, n - 1) where n is the number of bars.

class MinIdx_Segtree:
    def __init__(self, N, A):
        self.n = N
        self.INF = int(1e9)
        self.A = A
        while (self.n & (self.n - 1)) != 0:
            self.A.append(self.INF)
            self.n += 1
        self.tree = [0] * (2 * self.n)
        self.build()

    def build(self):
        for i in range(self.n):
            self.tree[self.n + i] = i
        for j in range(self.n - 1, 0, -1):
            a = self.tree[j << 1]
            b = self.tree[(j << 1) + 1]
            if self.A[a] <= self.A[b]:
                self.tree[j] = a
            else:
                self.tree[j] = b

    def update(self, i, val):
        self.A[i] = val
        j = (self.n + i) >> 1
        while j >= 1:
            a = self.tree[j << 1]
            b = self.tree[(j << 1) + 1]
            if self.A[a] <= self.A[b]:
                self.tree[j] = a
            else:
                self.tree[j] = b
            j >>= 1

    def query(self, ql, qh):
        return self._query(1, 0, self.n - 1, ql, qh)

    def _query(self, node, l, h, ql, qh):
        if ql > h or qh < l:
            return self.INF
        if l >= ql and h <= qh:
            return self.tree[node]
        a = self._query(node << 1, l, (l + h) >> 1, ql, qh)
        b = self._query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh)
        if a == self.INF:
            return b
        if b == self.INF:
            return a
        return a if self.A[a] <= self.A[b] else b

class Solution:
    def getMaxArea(self, heights, l, r, st):
        if l > r:
            return 0
        if l == r:
            return heights[l]
        minIdx = st.query(l, r)
        return max(max(self.getMaxArea(heights, l, minIdx - 1, st),
                       self.getMaxArea(heights, minIdx + 1, r, st)),
                   (r - l + 1) * heights[minIdx])

    def largestRectangleArea(self, heights):
        n = len(heights)
        st = MinIdx_Segtree(n, heights)
        return self.getMaxArea(heights, 0, n - 1, st)

public class MinIdx_Segtree {
    int n;
    final int INF = (int) 1e9;
    int[] A, tree;

    public MinIdx_Segtree(int N, int[] heights) {
        this.n = N;
        this.A = heights;
        while (Integer.bitCount(n) != 1) {
            A = java.util.Arrays.copyOf(A, n + 1);
            A[n] = INF;
            n++;
        }
        tree = new int[2 * n];
        build();
    }

    public void build() {
        for (int i = 0; i < n; i++) {
            tree[n + i] = i;
        }
        for (int j = n - 1; j >= 1; j--) {
            int a = tree[j << 1];
            int b = tree[(j << 1) + 1];
            if (A[a] <= A[b]) {
                tree[j] = a;
            } else {
                tree[j] = b;
            }
        }
    }

    public void update(int i, int val) {
        A[i] = val;
        for (int j = (n + i) >> 1; j >= 1; j >>= 1) {
            int a = tree[j << 1];
            int b = tree[(j << 1) + 1];
            if (A[a] <= A[b]) {
                tree[j] = a;
            } else {
                tree[j] = b;
            }
        }
    }

    public int query(int ql, int qh) {
        return query(1, 0, n - 1, ql, qh);
    }

    public int query(int node, int l, int h, int ql, int qh) {
        if (ql > h || qh < l) return INF;
        if (l >= ql && h <= qh) return tree[node];
        int a = query(node << 1, l, (l + h) >> 1, ql, qh);
        int b = query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh);
        if (a == INF) return b;
        if (b == INF) return a;
        return A[a] <= A[b] ? a : b;
    }
}

public class Solution {
    public int getMaxArea(int[] heights, int l, int r, MinIdx_Segtree st) {
        if (l > r) return 0;
        if (l == r) return heights[l];

        int minIdx = st.query(l, r);
        return Math.max(Math.max(getMaxArea(heights, l, minIdx - 1, st),
                                getMaxArea(heights, minIdx + 1, r, st)),
                        (r - l + 1) * heights[minIdx]);
    }

    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        MinIdx_Segtree st = new MinIdx_Segtree(n, heights);
        return getMaxArea(heights, 0, n - 1, st);
    }
}

class MinIdx_Segtree {
public:
    int n;
    const int INF = 1e9;
    vector<int> A;
    vector<int> tree;
    MinIdx_Segtree(int N, vector<int>& a) {
        this->n = N;
        this->A = a;
        while (__builtin_popcount(n) != 1) {
            A.push_back(INF);
            n++;
        }
        tree.resize(2 * n);
        build();
    }

    void build() {
        for (int i = 0; i < n; i++) {
            tree[n + i] = i;
        }
        for (int j = n - 1; j >= 1; j--) {
            int a = tree[j<<1];
            int b = tree[(j<<1) + 1];
            if(A[a]<=A[b])tree[j]=a;
            else tree[j] = b;
        }
    }

    void update(int i, int val) {
        A[i] = val;
        for (int j = (n + i) >> 1; j >= 1; j >>= 1) {
            int a = tree[j<<1];
            int b = tree[(j<<1) + 1];
            if(A[a]<=A[b])tree[j]=a;
            else tree[j] = b;
        }
    }

    int query(int ql, int qh) {
        return query(1, 0, n - 1, ql, qh);
    }

    int query(int node, int l, int h, int ql, int qh) {
        if (ql > h || qh < l) return INF;
        if (l >= ql && h <= qh) return tree[node];
        int a = query(node << 1, l, (l + h) >> 1, ql, qh);
        int b = query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh);
        if(a==INF)return b;
        if(b==INF)return a;
        return A[a]<=A[b]?a:b;
    }
};

class Solution {
public:
    int getMaxArea(vector<int>& heights, int l, int r, MinIdx_Segtree& st) {
        if (l > r) return 0;
        if (l == r) return heights[l];

        int minIdx = st.query(l, r);
        return max(max(getMaxArea(heights, l, minIdx - 1, st),
                   getMaxArea(heights, minIdx + 1, r, st)),
                   (r - l + 1) * heights[minIdx]);
    }
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        MinIdx_Segtree st(n, heights);
        return getMaxArea(heights, 0, n - 1, st);
    }
};

class MinIdx_Segtree {
    /**
     * @param {number} N
     * @param {number[]} heights
     */
    constructor(N, heights) {
        this.n = N;
        this.INF = 1e9;
        this.A = heights.slice();
        while ((this.n & (this.n - 1)) !== 0) {
            this.A.push(this.INF);
            this.n++;
        }
        this.tree = new Array(2 * this.n).fill(0);
        this.build();
    }

    build() {
        for (let i = 0; i < this.n; i++) {
            this.tree[this.n + i] = i;
        }
        for (let j = this.n - 1; j >= 1; j--) {
            let a = this.tree[j << 1];
            let b = this.tree[(j << 1) + 1];
            this.tree[j] = this.A[a] <= this.A[b] ? a : b;
        }
    }

    /**
     * @param {number} i
     * @param {number} val
     */
    update(i, val) {
        this.A[i] = val;
        for (let j = (this.n + i) >> 1; j >= 1; j >>= 1) {
            let a = this.tree[j << 1];
            let b = this.tree[(j << 1) + 1];
            this.tree[j] = this.A[a] <= this.A[b] ? a : b;
        }
    }

    /**
     * @param {number} ql
     * @param {number} qh
     * @return {number}
     */
    query(ql, qh) {
        return this._query(1, 0, this.n - 1, ql, qh);
    }

    _query(node, l, h, ql, qh) {
        if (ql > h || qh < l) return this.INF;
        if (l >= ql && h <= qh) return this.tree[node];
        let a = this._query(node << 1, l, (l + h) >> 1, ql, qh);
        let b = this._query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh);
        if (a === this.INF) return b;
        if (b === this.INF) return a;
        return this.A[a] <= this.A[b] ? a : b;
    }
}

class Solution {
    /**
     * @param {number[]} heights
     * @return {number}
     */
    largestRectangleArea(heights) {
        const n = heights.length;
        const st = new MinIdx_Segtree(n, heights);
        return this.getMaxArea(heights, 0, n - 1, st);
    }

    /**
     * @param {number[]} heights
     * @param {number} l
     * @param {number} r
     * @param {MinIdx_Segtree} st
     * @return {number}
     */
    getMaxArea(heights, l, r, st) {
        if (l > r) return 0;
        if (l === r) return heights[l];

        const minIdx = st.query(l, r);
        return Math.max(
            this.getMaxArea(heights, l, minIdx - 1, st),
            this.getMaxArea(heights, minIdx + 1, r, st),
            (r - l + 1) * heights[minIdx],
        );
    }
}

public class MinIdx_Segtree {
    private int n;
    private readonly int INF = (int)1e9;
    private int[] A, tree;

    public MinIdx_Segtree(int N, int[] heights) {
        this.n = N;
        this.A = new int[heights.Length];
        heights.CopyTo(this.A, 0);
        while ((n & (n - 1)) != 0) {
            Array.Resize(ref A, n + 1);
            A[n] = INF;
            n++;
        }
        tree = new int[2 * n];
        Build();
    }

    private void Build() {
        for (int i = 0; i < n; i++) {
            tree[n + i] = i;
        }
        for (int j = n - 1; j >= 1; j--) {
            int a = tree[j << 1];
            int b = tree[(j << 1) + 1];
            tree[j] = A[a] <= A[b] ? a : b;
        }
    }

    public int Query(int ql, int qh) {
        return Query(1, 0, n - 1, ql, qh);
    }

    private int Query(int node, int l, int h, int ql, int qh) {
        if (ql > h || qh < l) return INF;
        if (l >= ql && h <= qh) return tree[node];
        int a = Query(node << 1, l, (l + h) >> 1, ql, qh);
        int b = Query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh);
        if (a == INF) return b;
        if (b == INF) return a;
        return A[a] <= A[b] ? a : b;
    }
}

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int n = heights.Length;
        MinIdx_Segtree st = new MinIdx_Segtree(n, heights);
        return GetMaxArea(heights, 0, n - 1, st);
    }

    private int GetMaxArea(int[] heights, int l, int r, MinIdx_Segtree st) {
        if (l > r) return 0;
        if (l == r) return heights[l];

        int minIdx = st.Query(l, r);
        return Math.Max(
            Math.Max(GetMaxArea(heights, l, minIdx - 1, st),
                    GetMaxArea(heights, minIdx + 1, r, st)),
                    (r - l + 1) * heights[minIdx]);
    }
}

type MinIdxSegtree struct {
    n   int
    INF int
    A   []int
    tree []int
}

func NewMinIdxSegtree(N int, A []int) *MinIdxSegtree {
    st := &MinIdxSegtree{
        n:   N,
        INF: 1000000000,
        A:   make([]int, N),
    }
    copy(st.A, A)

    for (st.n & (st.n - 1)) != 0 {
        st.A = append(st.A, st.INF)
        st.n++
    }

    st.tree = make([]int, 2*st.n)
    st.build()
    return st
}

func (st *MinIdxSegtree) build() {
    for i := 0; i < st.n; i++ {
        st.tree[st.n+i] = i
    }

    for j := st.n - 1; j > 0; j-- {
        a := st.tree[j<<1]
        b := st.tree[(j<<1)+1]
        if st.A[a] <= st.A[b] {
            st.tree[j] = a
        } else {
            st.tree[j] = b
        }
    }
}

func (st *MinIdxSegtree) update(i, val int) {
    st.A[i] = val
    j := (st.n + i) >> 1
    for j >= 1 {
        a := st.tree[j<<1]
        b := st.tree[(j<<1)+1]
        if st.A[a] <= st.A[b] {
            st.tree[j] = a
        } else {
            st.tree[j] = b
        }
        j >>= 1
    }
}

func (st *MinIdxSegtree) query(ql, qh int) int {
    return st.queryHelper(1, 0, st.n-1, ql, qh)
}

func (st *MinIdxSegtree) queryHelper(node, l, h, ql, qh int) int {
    if ql > h || qh < l {
        return st.INF
    }
    if l >= ql && h <= qh {
        return st.tree[node]
    }
    a := st.queryHelper(node<<1, l, (l+h)>>1, ql, qh)
    b := st.queryHelper((node<<1)+1, ((l+h)>>1)+1, h, ql, qh)
    if a == st.INF {
        return b
    }
    if b == st.INF {
        return a
    }
    if st.A[a] <= st.A[b] {
        return a
    }
    return b
}

func getMaxArea(heights []int, l, r int, st *MinIdxSegtree) int {
    if l > r {
        return 0
    }
    if l == r {
        return heights[l]
    }
    minIdx := st.query(l, r)
    area1 := getMaxArea(heights, l, minIdx-1, st)
    area2 := getMaxArea(heights, minIdx+1, r, st)
    area3 := (r - l + 1) * heights[minIdx]

    maxArea := area1
    if area2 > maxArea {
        maxArea = area2
    }
    if area3 > maxArea {
        maxArea = area3
    }
    return maxArea
}

func largestRectangleArea(heights []int) int {
    n := len(heights)
    st := NewMinIdxSegtree(n, heights)
    return getMaxArea(heights, 0, n-1, st)
}

class MinIdxSegtree(private var n: Int, input: IntArray) {
    private val INF = 1000000000
    private val A: IntArray
    private val tree: IntArray

    init {
        var size = n
        while (size and (size - 1) != 0) size++
        A = IntArray(size) { if (it < n) input[it] else INF }
        n = size
        tree = IntArray(2 * n)
        for (i in 0 until n) tree[n + i] = i
        for (j in n - 1 downTo 1) {
            val left = tree[j shl 1]
            val right = tree[j shl 1 or 1]
            tree[j] = if (A[left] <= A[right]) left else right
        }
    }

    fun query(ql: Int, qh: Int): Int = queryHelper(1, 0, n - 1, ql, qh)

    private fun queryHelper(node: Int, l: Int, h: Int, ql: Int, qh: Int): Int {
        if (ql > h || qh < l) return INF
        if (l >= ql && h <= qh) return tree[node]

        val mid = (l + h) shr 1
        val a = queryHelper(node shl 1, l, mid, ql, qh)
        val b = queryHelper((node shl 1) + 1, mid + 1, h, ql, qh)

        return when {
            a == INF -> b
            b == INF -> a
            A[a] <= A[b] -> a
            else -> b
        }
    }
}

class Solution {
    fun largestRectangleArea(heights: IntArray): Int {
        val n = heights.size
        val st = MinIdxSegtree(n, heights)

        fun getMaxArea(l: Int, r: Int): Int {
            if (l > r) return 0
            if (l == r) return heights[l]
            val minIdx = st.query(l, r)
            val area = (r - l + 1) * heights[minIdx]
            val leftArea = getMaxArea(l, minIdx - 1)
            val rightArea = getMaxArea(minIdx + 1, r)
            return maxOf(area, leftArea, rightArea)
        }

        return getMaxArea(0, n - 1)
    }
}

class MinIdxSegmentTree {
    private var n: Int
    private var INF = Int(1e9)
    private var A: [Int]
    private var tree: [Int]

    init(_ N: Int, _ A: [Int]) {
        self.n = N
        self.A = A
        while (self.n & (self.n - 1)) != 0 {
            self.A.append(self.INF)
            self.n += 1
        }
        self.tree = [Int](repeating: 0, count: 2 * self.n)
        build()
    }

    private func build() {
        for i in 0..<n {
            tree[n + i] = i
        }
        for j in stride(from: n - 1, through: 1, by: -1) {
            let a = tree[j << 1]
            let b = tree[(j << 1) + 1]
            tree[j] = (A[a] <= A[b]) ? a : b
        }
    }

    func update(_ i: Int, _ val: Int) {
        A[i] = val
        var j = (n + i) >> 1
        while j >= 1 {
            let a = tree[j << 1]
            let b = tree[(j << 1) + 1]
            tree[j] = (A[a] <= A[b]) ? a : b
            j >>= 1
        }
    }

    func query(_ ql: Int, _ qh: Int) -> Int {
        return _query(1, 0, n - 1, ql, qh)
    }

    private func _query(_ node: Int, _ l: Int, _ h: Int, _ ql: Int, _ qh: Int) -> Int {
        if ql > h || qh < l {
            return INF
        }
        if l >= ql && h <= qh {
            return tree[node]
        }
        let a = _query(node << 1, l, (l + h) >> 1, ql, qh)
        let b = _query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh)
        if a == INF { return b }
        if b == INF { return a }
        return (A[a] <= A[b]) ? a : b
    }
}

class Solution {
    func getMaxArea(_ heights: [Int], _ l: Int, _ r: Int, _ st: MinIdxSegmentTree) -> Int {
        if l > r { return 0 }
        if l == r { return heights[l] }

        let minIdx = st.query(l, r)
        return max(
            max(getMaxArea(heights, l, minIdx - 1, st),
                getMaxArea(heights, minIdx + 1, r, st)),
            (r - l + 1) * heights[minIdx]
        )
    }

    func largestRectangleArea(_ heights: [Int]) -> Int {
        let n = heights.count
        let st = MinIdxSegmentTree(n, heights)
        return getMaxArea(heights, 0, n - 1, st)
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Stack

Intuition

For each bar, we want to know how far it can stretch left and right before bumping into a shorter bar.
That distance tells us the widest rectangle where this bar is the limiting height.
To efficiently find the nearest smaller bar on both sides, we use a monotonic stack that keeps indices of bars in increasing height order.
This lets us compute boundaries in linear time instead of checking outward for every bar.

Algorithm

Use a stack to find, for each index i, the nearest smaller bar on the left:
- If the current bar is shorter than the bar on top of the stack, pop until this is no longer true.
- The top of the stack becomes the left boundary.
- If the stack is empty, no smaller bar exists, so left boundary is -1.
Repeat the same process from right to left to find the nearest smaller bar on the right:
- If no smaller bar exists, the right boundary is n.
For each bar:
- Expand between the boundaries and compute its max rectangle:
  height[i] * (right - left - 1)
Return the largest area found.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        stack = []

        leftMost = [-1] * n
        for i in range(n):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                leftMost[i] = stack[-1]
            stack.append(i)

        stack = []
        rightMost = [n] * n
        for i in range(n - 1, -1, -1):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                rightMost[i] = stack[-1]
            stack.append(i)

        maxArea = 0
        for i in range(n):
            leftMost[i] += 1
            rightMost[i] -= 1
            maxArea = max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1))
        return maxArea

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] leftMost = new int[n];
        int[] rightMost = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            leftMost[i] = -1;
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                leftMost[i] = stack.peek();
            }
            stack.push(i);
        }

        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            rightMost[i] = n;
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                rightMost[i] = stack.peek();
            }
            stack.push(i);
        }

        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            leftMost[i] += 1;
            rightMost[i] -= 1;
            maxArea = Math.max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1));
        }
        return maxArea;
    }
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> leftMost(n, -1);
        vector<int> rightMost(n, n);
        stack<int> stack;

        for (int i = 0; i < n; i++) {
            while (!stack.empty() && heights[stack.top()] >= heights[i]) {
                stack.pop();
            }
            if (!stack.empty()) {
                leftMost[i] = stack.top();
            }
            stack.push(i);
        }

        while (!stack.empty()) stack.pop();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.empty() && heights[stack.top()] >= heights[i]) {
                stack.pop();
            }
            if (!stack.empty()) {
                rightMost[i] = stack.top();
            }
            stack.push(i);
        }

        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            leftMost[i] += 1;
            rightMost[i] -= 1;
            maxArea = max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1));
        }

        return maxArea;
    }
};

class Solution {
    /**
     * @param {number[]} heights
     * @return {number}
     */
    largestRectangleArea(heights) {
        const n = heights.length;
        const leftMost = Array(n).fill(-1);
        const rightMost = Array(n).fill(n);
        const stack = [];

        for (let i = 0; i < n; i++) {
            while (
                stack.length &&
                heights[stack[stack.length - 1]] >= heights[i]
            ) {
                stack.pop();
            }
            if (stack.length) {
                leftMost[i] = stack[stack.length - 1];
            }
            stack.push(i);
        }

        stack.length = 0;
        for (let i = n - 1; i >= 0; i--) {
            while (
                stack.length &&
                heights[stack[stack.length - 1]] >= heights[i]
            ) {
                stack.pop();
            }
            if (stack.length) {
                rightMost[i] = stack[stack.length - 1];
            }
            stack.push(i);
        }

        let maxArea = 0;
        for (let i = 0; i < n; i++) {
            leftMost[i] += 1;
            rightMost[i] -= 1;
            maxArea = Math.max(
                maxArea,
                heights[i] * (rightMost[i] - leftMost[i] + 1),
            );
        }

        return maxArea;
    }
}

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int n = heights.Length;
        int[] leftMost = new int[n];
        int[] rightMost = new int[n];
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < n; i++) {
            leftMost[i] = -1;
            while (stack.Count > 0 && heights[stack.Peek()] >= heights[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) {
                leftMost[i] = stack.Peek();
            }
            stack.Push(i);
        }

        stack.Clear();
        for (int i = n - 1; i >= 0; i--) {
            rightMost[i] = n;
            while (stack.Count > 0 && heights[stack.Peek()] >= heights[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) {
                rightMost[i] = stack.Peek();
            }
            stack.Push(i);
        }

        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            leftMost[i] += 1;
            rightMost[i] -= 1;
            maxArea = Math.Max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1));
        }

        return maxArea;
    }
}

func largestRectangleArea(heights []int) int {
    n := len(heights)
    stack := make([]int, 0)

    leftMost := make([]int, n)
    for i := range leftMost {
        leftMost[i] = -1
    }

    for i := 0; i < n; i++ {
        for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            leftMost[i] = stack[len(stack)-1]
        }
        stack = append(stack, i)
    }

    stack = stack[:0]
    rightMost := make([]int, n)
    for i := range rightMost {
        rightMost[i] = n
    }

    for i := n - 1; i >= 0; i-- {
        for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            rightMost[i] = stack[len(stack)-1]
        }
        stack = append(stack, i)
    }

    maxArea := 0
    for i := 0; i < n; i++ {
        leftMost[i]++
        rightMost[i]--
        area := heights[i] * (rightMost[i] - leftMost[i] + 1)
        if area > maxArea {
            maxArea = area
        }
    }

    return maxArea
}

class Solution {
    fun largestRectangleArea(heights: IntArray): Int {
        val n = heights.size
        val stack = ArrayDeque<Int>()

        val leftMost = IntArray(n) { -1 }
        for (i in 0 until n) {
            while (stack.isNotEmpty() && heights[stack.last()] >= heights[i]) {
                stack.removeLast()
            }
            if (stack.isNotEmpty()) {
                leftMost[i] = stack.last()
            }
            stack.addLast(i)
        }

        stack.clear()
        val rightMost = IntArray(n) { n }
        for (i in n - 1 downTo 0) {
            while (stack.isNotEmpty() && heights[stack.last()] >= heights[i]) {
                stack.removeLast()
            }
            if (stack.isNotEmpty()) {
                rightMost[i] = stack.last()
            }
            stack.addLast(i)
        }

        var maxArea = 0
        for (i in 0 until n) {
            leftMost[i]++
            rightMost[i]--
            maxArea = maxOf(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1))
        }

        return maxArea
    }
}

class Solution {
    func largestRectangleArea(_ heights: [Int]) -> Int {
        let n = heights.count
        var stack = [Int]()

        var leftMost = [Int](repeating: -1, count: n)
        for i in 0..<n {
            while !stack.isEmpty && heights[stack.last!] >= heights[i] {
                stack.removeLast()
            }
            if !stack.isEmpty {
                leftMost[i] = stack.last!
            }
            stack.append(i)
        }

        stack.removeAll()
        var rightMost = [Int](repeating: n, count: n)
        for i in stride(from: n - 1, through: 0, by: -1) {
            while !stack.isEmpty && heights[stack.last!] >= heights[i] {
                stack.removeLast()
            }
            if !stack.isEmpty {
                rightMost[i] = stack.last!
            }
            stack.append(i)
        }

        var maxArea = 0
        for i in 0..<n {
            leftMost[i] += 1
            rightMost[i] -= 1
            maxArea = max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1))
        }
        return maxArea
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Stack (One Pass)

Intuition

We want, for each bar, the widest area where it can act as the shortest bar.
With a single pass and a stack, we can do this on the fly:

We keep a stack of bars in increasing height order, each stored with the earliest index where that height can start.
When we see a new bar that is shorter than the top of the stack, it means the taller bar on top can’t extend further to the right.
- So we pop it and compute the area it could cover.
The new shorter bar can start from as far left as the popped bar’s start index, so we reuse that index.
After the pass, we compute areas for any bars still in the stack, extending them to the end.

Each bar is pushed and popped at most once, giving an efficient, one-pass solution.

Algorithm

Initialize:
- An empty stack to store pairs (start_index, height).
- maxArea = 0.
Traverse the histogram from left to right with index i and height h:
- Set start = i.
- While the stack is not empty and the top height is greater than h:
  - Pop (index, height) from the stack.
  - Update maxArea with height * (i - index).
  - Set start = index (the new bar can start from here).
- Push (start, h) onto the stack.
After the loop, process remaining bars in the stack:
- For each (index, height) in the stack:
  - Update maxArea with height * (n - index), where n is the total number of bars.
Return maxArea.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = []  # pair: (index, height)

        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                start = index
            stack.append((start, h))

        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))
        return maxArea

class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        Stack<int[]> stack = new Stack<>(); // pair: (index, height)

        for (int i = 0; i < heights.length; i++) {
            int start = i;
            while (!stack.isEmpty() && stack.peek()[1] > heights[i]) {
                int[] top = stack.pop();
                int index = top[0];
                int height = top[1];
                maxArea = Math.max(maxArea, height * (i - index));
                start = index;
            }
            stack.push(new int[]{start, heights[i]});
        }

        for (int[] pair : stack) {
            int index = pair[0];
            int height = pair[1];
            maxArea = Math.max(maxArea, height * (heights.length - index));
        }
        return maxArea;
    }
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxArea = 0;
        stack<pair<int, int>> stack; // pair: (index, height)

        for (int i = 0; i < heights.size(); i++) {
            int start = i;
            while (!stack.empty() && stack.top().second > heights[i]) {
                pair<int, int> top = stack.top();
                int index = top.first;
                int height = top.second;
                maxArea = max(maxArea, height * (i - index));
                start = index;
                stack.pop();
            }
            stack.push({ start, heights[i] });
        }

        while (!stack.empty()) {
            int index = stack.top().first;
            int height = stack.top().second;
            maxArea = max(maxArea, height * (static_cast<int>(heights.size()) - index));
            stack.pop();
        }
        return maxArea;
    }
};

class Solution {
    /**
     * @param {number[]} heights
     * @return {number}
     */
    largestRectangleArea(heights) {
        let maxArea = 0;
        const stack = []; // pair: (index, height)

        for (let i = 0; i < heights.length; i++) {
            let start = i;
            while (
                stack.length > 0 &&
                stack[stack.length - 1][1] > heights[i]
            ) {
                const [index, height] = stack.pop();
                maxArea = Math.max(maxArea, height * (i - index));
                start = index;
            }
            stack.push([start, heights[i]]);
        }

        for (const [index, height] of stack) {
            maxArea = Math.max(maxArea, height * (heights.length - index));
        }
        return maxArea;
    }
}

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int maxArea = 0;
        Stack<int[]> stack = new Stack<int[]>(); // pair: (index, height)

        for (int i = 0; i < heights.Length; i++) {
            int start = i;
            while (stack.Count > 0 && stack.Peek()[1] > heights[i]) {
                int[] top = stack.Pop();
                int index = top[0];
                int height = top[1];
                maxArea = Math.Max(maxArea, height * (i - index));
                start = index;
            }
            stack.Push(new int[] { start, heights[i] });
        }

        foreach (int[] pair in stack) {
            int index = pair[0];
            int height = pair[1];
            maxArea = Math.Max(maxArea, height * (heights.Length - index));
        }
        return maxArea;
    }
}

func largestRectangleArea(heights []int) int {
    maxArea := 0
    stack := make([][2]int, 0)

    for i, h := range heights {
        start := i
        for len(stack) > 0 && stack[len(stack)-1][1] > h {
            index := stack[len(stack)-1][0]
            height := stack[len(stack)-1][1]
            stack = stack[:len(stack)-1]
            area := height * (i - index)
            if area > maxArea {
                maxArea = area
            }
            start = index
        }
        stack = append(stack, [2]int{start, h})
    }

    n := len(heights)
    for _, pair := range stack {
        area := pair[1] * (n - pair[0])
        if area > maxArea {
            maxArea = area
        }
    }

    return maxArea
}

class Solution {
    fun largestRectangleArea(heights: IntArray): Int {
        var maxArea = 0
        val stack = ArrayDeque<Pair<Int, Int>>()

        heights.forEachIndexed { i, h ->
            var start = i
            while (stack.isNotEmpty() && stack.last().second > h) {
                val (index, height) = stack.removeLast()
                maxArea = maxOf(maxArea, height * (i - index))
                start = index
            }
            stack.addLast(start to h)
        }

        val n = heights.size
        for ((i, h) in stack) {
            maxArea = maxOf(maxArea, h * (n - i))
        }

        return maxArea
    }
}

class Solution {
    func largestRectangleArea(_ heights: [Int]) -> Int {
        var maxArea = 0
        var stack = [(Int, Int)]() // Pair: (index, height)

        for (i, h) in heights.enumerated() {
            var start = i
            while !stack.isEmpty && stack.last!.1 > h {
                let (index, height) = stack.removeLast()
                maxArea = max(maxArea, height * (i - index))
                start = index
            }
            stack.append((start, h))
        }

        for (i, h) in stack {
            maxArea = max(maxArea, h * (heights.count - i))
        }

        return maxArea
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Stack (Optimal)

Intuition

We want, for every bar, to know how wide it can stretch while still being the shortest bar in that rectangle.

A monotonic stack helps with this:

We keep a stack of indices where the bar heights are in increasing order.
As long as the next bar is taller or equal, we keep pushing indices.
When we see a shorter bar, it means the bar on top of the stack can’t extend further to the right:
- We pop it and treat it as the height of a rectangle.
- Its width goes from the new top of the stack + 1 up to the current index − 1.

To make sure every bar eventually gets popped and processed, we run the loop one extra step with a “virtual” bar of height 0 at the end.
Each bar is pushed and popped at most once, so this is both optimal and clean.

Algorithm

Initialize:
- maxArea = 0
- An empty stack to store indices of bars (with heights in increasing order).
Loop i from 0 to n (inclusive):
- While the stack is not empty and either:
  - i == n (we're past the last bar, acting like height 0), or
  - heights[i] is less than or equal to the height at the top index of the stack:
    - Pop the top index; let its height be h.
    - Compute the width:
      - If the stack is empty, width = i (it extends from 0 to i - 1).
      - Otherwise, width = i - stack.top() - 1.
    - Update maxArea with h * width.
- Push the current index i onto the stack.
After the loop, maxArea holds the largest rectangle area. Return it.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        maxArea = 0
        stack = []

        for i in range(n + 1):
            while stack and (i == n  or heights[stack[-1]] >= heights[i]):
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                maxArea = max(maxArea, height * width)
            stack.append(i)
        return maxArea

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i <= n; i++) {
            while (!stack.isEmpty() &&
                 (i == n || heights[stack.peek()] >= heights[i])) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int maxArea = 0;
        stack<int> stack;

        for (int i = 0; i <= n; i++) {
            while (!stack.empty() &&
                 (i == n || heights[stack.top()] >= heights[i])) {
                int height = heights[stack.top()];
                stack.pop();
                int width = stack.empty() ? i : i - stack.top() - 1;
                maxArea = max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
};

class Solution {
    /**
     * @param {number[]} heights
     * @return {number}
     */
    largestRectangleArea(heights) {
        const n = heights.length;
        let maxArea = 0;
        const stack = [];

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

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int n = heights.Length;
        int maxArea = 0;
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i <= n; i++) {
            while (stack.Count > 0 &&
                 (i == n || heights[stack.Peek()] >= heights[i])) {
                int height = heights[stack.Pop()];
                int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
                maxArea = Math.Max(maxArea, height * width);
            }
            stack.Push(i);
        }
        return maxArea;
    }
}

func largestRectangleArea(heights []int) int {
    n := len(heights)
    maxArea := 0
    stack := make([]int, 0)

    for i := 0; i <= n; i++ {
        for len(stack) > 0 && (i == n || heights[stack[len(stack)-1]] >= heights[i]) {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]

            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }

            area := height * width
            if area > maxArea {
                maxArea = area
            }
        }
        if i < n {
            stack = append(stack, i)
        }
    }

    return maxArea
}

class Solution {
    fun largestRectangleArea(heights: IntArray): Int {
        val n = heights.size
        var maxArea = 0
        val stack = ArrayDeque<Int>()

        for (i in 0..n) {
            while (stack.isNotEmpty() && (i == n || heights[stack.last()] >= heights[i])) {
                val height = heights[stack.removeLast()]
                val width = if (stack.isEmpty()) i else i - stack.last() - 1
                maxArea = maxOf(maxArea, height * width)
            }
            if (i < n) stack.addLast(i)
        }

        return maxArea
    }
}

class Solution {
    func largestRectangleArea(_ heights: [Int]) -> Int {
        let n = heights.count
        var maxArea = 0
        var stack = [Int]()

        for i in 0...n {
            while !stack.isEmpty && (i == n || heights[stack.last!] >= heights[i]) {
                let height = heights[stack.removeLast()]
                let width = stack.isEmpty ? i : i - stack.last! - 1
                maxArea = max(maxArea, height * width)
            }
            stack.append(i)
        }
        return maxArea
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Off-by-One Errors in Width Calculation

When computing the width of a rectangle, it is easy to miscalculate the boundaries. The width should be right - left - 1 when left and right are the indices of the nearest smaller bars (exclusive boundaries). Forgetting to subtract 1 or using inclusive boundaries incorrectly leads to wrong area calculations.

Forgetting to Process Remaining Stack Elements

After iterating through all bars, the stack may still contain indices of bars that never encountered a shorter bar to their right. These bars can extend all the way to the end of the histogram. Failing to pop and process these remaining elements misses potentially valid rectangles.

Using Strict vs Non-Strict Inequality

When comparing heights to decide whether to pop from the stack, using > versus >= matters. Using strict greater-than may cause bars of equal height to remain on the stack incorrectly, leading to wrong boundary calculations. The choice depends on how you handle the left boundary for bars with equal heights.

Incorrect Handling of Empty Stack

When the stack becomes empty while computing the left boundary, it means no shorter bar exists to the left. The width should extend from index 0 to the current position. Using stack[-1] or stack.top() on an empty stack causes runtime errors or incorrect results if not handled explicitly.

Not Handling Single-Element Arrays

Edge cases like arrays with a single bar or all bars having the same height require careful handling. The algorithm should correctly return the height of the single bar or the product of height and array length for uniform arrays without special-case bugs.