Largest Rectangle in Histogram

Imagine you're analyzing stock prices represented as a histogram, where each bar's height corresponds to the price on a given day. The goal is to find the largest possible rectangle that can be inscribed within this histogram. This problem is a classic algorithmic challenge with applications in areas like data analysis and image processing.

Problem Description

Given an array of integers representing the heights of bars in a histogram, determine the area of the largest rectangle that can be formed within the histogram. Each bar has a width of 1. The rectangle must be entirely within the bounds of the histogram.

What needs to be achieved: Calculate the maximum rectangular area possible within the given histogram.

Key requirements:

• The rectangle must be formed using adjacent bars in the histogram.
• The height of the rectangle is limited by the shortest bar within its width.

Expected behavior: The function should return an integer representing the maximum rectangular area.

Edge cases to consider:

• Empty histogram (input array is empty).
• Histogram with all bars of height 0.
• Histogram with a single bar.
• Histograms with varying bar heights, including cases where the largest rectangle spans the entire histogram or is contained within a smaller section.

Examples

Example 1:

Input: [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The largest rectangle is formed by bars with heights 5 and 6, spanning a width of 2.  Area = 6 * 2 = 10.

Example 2:

Input: [2, 4]
Output: 4
Explanation: The largest rectangle is formed by the bar with height 2, spanning a width of 1. Area = 2 * 1 = 2.  However, the bar with height 4 spanning a width of 1 gives an area of 4, which is larger.

Example 3:

Input: [0, 0, 0]
Output: 0
Explanation: All bars have height 0, so the largest rectangle has an area of 0.

Example 4:

Input: [4, 2, 0, 3, 2, 5]
Output: 6
Explanation: The largest rectangle is formed by the bars with heights 3 and 2, spanning a width of 2. Area = 3 * 2 = 6.

Constraints

• The input array will contain non-negative integers.
• The length of the input array will be between 0 and 100,000.
• Each bar height will be between 0 and 10,000.
• The solution should ideally have a time complexity of O(n), where n is the number of bars in the histogram. A brute-force O(n^2) solution will be considered less efficient.

Notes

Consider using a stack-based approach to efficiently track potential rectangle boundaries. The stack will store indices of bars, allowing you to quickly determine the width of a rectangle when you encounter a bar that is shorter than the top of the stack. Think about how to handle the case when the stack is empty or when the current bar is shorter than all bars in the stack. The key is to efficiently find the left and right boundaries for each bar, considering it as the minimum height of a potential rectangle.