Largest Rectangle in Histogram

 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

🧠 Logic:

1. For each bar at index i, find:

   • left[i] → Index of previous smaller element on the left.

   • right[i] → Index of next smaller element on the right.

2. For each bar:

   • Width = right[i] - left[i] - 1

   • Area = heights[i] * width

3. Return the maximum area.

🔍 Example Dry Run: heights = [2, 1, 5, 6, 2, 3]

• Right smaller (traversing left to right):

  • Right: [1, 6, 4, 4, 6, 6]

• Left smaller (traversing right to left):

  • Left: [-1, -1, 1, 2, 1, 4]

Then use width: right[i] - left[i] - 1 for area.

class Solution {

    public int largestRectangleArea(int[] heights) {

         int n = heights.length;

        int[] left = new int[n];   // Index of previous smaller element

        int[] right = new int[n];  // Index of next smaller element

        Stack<Integer> st = new Stack<>();

        // 1️⃣ Right Smaller Element → Traverse left to right

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

            while (!st.isEmpty() && heights[st.peek()] > heights[i]) {

                int index = st.pop();

                right[index] = i;

            }

            st.push(i);

        }

        // Fill remaining with n (no smaller to the right)

        while (!st.isEmpty()) {

            right[st.pop()] = n;

        }

        // 2️⃣ Left Smaller Element → Traverse right to left

        st.clear();

        for (int i = n - 1; i >= 0; i--) {

            while (!st.isEmpty() && heights[st.peek()] > heights[i]) {

                int index = st.pop();

                left[index] = i;

            }

            st.push(i);

        }

        // Fill remaining with -1 (no smaller to the left)

        while (!st.isEmpty()) {

            left[st.pop()] = -1;

        }

        // 3️⃣ Calculate max area

        int maxArea = 0;

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

            int width = right[i] - left[i] - 1;

            int area = heights[i] * width;

            maxArea = Math.max(maxArea, area);

        }

        return maxArea;

    }

}