Find Maximum Rectangle in Bar Chart
Company: Palo Alto Networks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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:**
```text
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:**
```text
Input: heights = [2, 4]
Output: 4
```
**Constraints:**
- `1 <= n <= 100000`
- `0 <= heights[i] <= 1000000000`
- The answer fits in a 64-bit signed integer.
Overview: 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.
Read the full Palo Alto Networks Software Engineer interview experience this question came from
Return the maximum rectangle area in a bar chart.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([2,1,5,6,2,3],)
Expected Output: 10
Explanation: Best rectangle area is 10.
Input: ([2,4],)
Expected Output: 4
Explanation: Best area is 4.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.