Coding questions · Palo Alto Networks

Find Maximum Rectangle in Bar Chart

This question evaluates algorithmic problem-solving and data structure proficiency in computing the maximum rectangular area within a histogram-like array, focusing on contiguous segment analysis and range-based aggregation.

Given an array heights of n non-negative integers, where each value represents the height of a vertical bar in a bar chart and every bar has width 1, find the maximum possible rectangular area that can be formed by choosing one or more consecutive bars.

A rectangle spanning bars i through j has height equal to the minimum height among those bars and width j - i + 1.

Return the maximum area.

Example 1:

Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The best rectangle spans the bars with heights 5 and 6, giving area 5 * 2 = 10.

Example 2:

Input: heights = [2, 4]
Output: 4

Constraints:

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

Largest Rectangle In Histogram

Hints

Clarify edge cases before coding.
Keep the return value deterministic.