Largest Rectangle in Histogram
Monotonic Stack & Queue Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Finding the Largest Rectangle in a Histogram, Arrays, Stack, Brute Force, Optimization, Time Complexity, Space Complexity, Monotonic Stack, space complexity, brute force, stack, frequency counting, divide and conquer, algorithm design, monotonic stack, array traversal, time complexity analysis, Largest Rectangle in Histogram, Next/Previous Greater/Smaller Element.
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: Input: N = 6, heights[] = {2,1,5,6,2,3} Output: 10 Explanation: The largest rectangle area is 10, formed by bars of height 5 and 6 (index 2 and 3) with a minimum height of 5, giving a width of 2, thus area 5 2 = 10. Another example is the bar of height 1 (index 1), which can extend across the whole given segment (width 6), giving an area of 1 6 = 6. (Note: The problem description's provided example output 10 corresponds to the input {2,1,5,6,2,3}. The internal code example arr[] = {2, 1, 5, 6, 2, 3, 1} leads to 10 as well. I will stick to the problem statement's given example for clarity.)