Largest Container

Find the largest rectangular area possible within a histogram defined by an array of heights. This problem showcases your ability to optimize a solution from quadratic to linear time, a key skill for efficient algorithm design.

arraystackhistogramareaoptimization

Problem Statement

Given an array of non-negative integers representing the heights of bars in a histogram where each bar has a width of 1, find the largest rectangular area that can be fit within the histogram. The area is calculated by multiplying the height of a rectangle by its width.

Example 1

Input: [2, 1, 5, 6, 2, 3]

Output: 10

The largest rectangle is formed between the bars of heights 5 and 6, with a height of 5 and a width of 2, resulting in an area of 10.

Example 2

Input: [4, 2, 0, 3, 2, 5]

Output: 6

The largest rectangle is formed by the bar of height 3, extending to the left and right until it encounters bars of height 0, giving a width of 2 and an area of 6.

Constraints

-1 <= heights.length <= 10^5
-0 <= heights[i] <= 10^4
-The input array contains non-negative integers.
-Each bar has a width of 1.

Brute Force Approach

Imagine trying every possible rectangle by iterating through all possible start and end points within the histogram. For each pair, calculate the area and keep track of the maximum. This is like trying to fit every possible cardboard box shape within the histogram to see which one fits best and is largest. This involves checking every possible sub-array.

TimeO(n^2)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem