Largest Rectangle in a Histogram Problem

Largest Rectangle in a Histogram Problem — ExecCode Medium DSA Practice

Solve the Largest Rectangle in a Histogram problem on ExecCode. Free online medium DSA practice in Stacks & Queues. Write and run code in Java, C++, Python — no signup required to run.

Problem description

You are given an array h, where h[i] is the height of a histogram bar. Each bar has width 1. Return the area of the largest rectangle that can be formed using one or more consecutive bars. Use a 64-bit integer. You are given: h — bar heights Return the largest rectangle area as a 64-bit integer. The rectangle must use consecutive bars. Its height is the shortest bar it covers, and its width is the number of bars. A monotonic stack finds, for each bar, the widest rectangle with that bar as the shortest.

Examples

Input {'h': [2, 1, 5, 6, 2, 3]}; Output 10. Input {'h': [2, 4]}; Output 4. Input {'h': [5, 5, 5]}; Output 15

Constraints

1 <= h.length <= 100000 0 <= h[i] <= 1000000000 The answer fits in a signed 64-bit integer

Practice Largest Rectangle in a Histogram free on ExecCode. Browse DSA problems, topic map, and placement guides.