Problem Description

The task is to find the largest rectangular area in a histogram, which consists of a series of adjacent bars of varying heights. Each bar has a uniform width of 1 unit, and the height of each bar corresponds to each integer in the given heights array. To elaborate, imagine drawing rectangles starting from the base of each bar and extending them as wide as possible without crossing the height of shorter bars adjacent to it. The goal is to determine the maximum area covered by such a rectangle.

Intuition

The intuition behind the solution involves using a stack and a concept called "Monotonic Stack" which helps us process the bars in a way that we can calculate the maximum width for each bar where it remains the tallest bar within that width.

Here is the reasoning for each step in the algorithm:

• We initialize left and right arrays to keep track of the bounds for the largest rectangle with height[i] as the smallest bar. left[i] will store the index of the first bar to the left that is shorter than height[i], and right[i] will store the index of the first bar to the right that is shorter than height[i].

• We traverse the heights while using a stack stk to maintain indices of bars in a non-decreasing order. The stack will help us in finding the left and right bounds for each bar.

• For each bar h with index i:

  • We pop from the stack while the bar at the top of the stack has a height greater than or equal to h. Each time we pop, we update the right bound for the popped index because we just found a shorter bar on the right.
  • If the stack is not empty after popping, it means the bar on the top of the stack is the first bar to the left of h that is shorter, so we update the left[i] to that index.
  • We then push i onto the stack, since it might be the potential left bound for a future bar.

• After we have the left and right bounds for each bar, the maximum possible width for each bar is given as (right[i] - left[i] - 1). We multiply this with the height heights[i] of the bar to get the area of the largest rectangle with the bar at i being the shortest bar. We calculate this for every bar.

• Finally, we return the maximum area out of all the areas we have computed.

This algorithm is efficient because each bar is pushed and popped from the stack exactly once, and the left and right bounds are updated during this process. We're leveraging the stack to perform all necessary computations as we iterate through the histogram, which allows us to compute the largest rectangle in linear time.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The solution is implemented in Python using a single-pass algorithm with a stack data structure to maintain a history of bars that are yet to find a shorter bar on the right. The goal is to calculate the correct left and right bounds for each bar, which will then allow us to calculate the area of the largest rectangle that can be formed with each bar as the shortest one in that rectangle.

Here's a step-by-step breakdown of the algorithm:

1. Initializing Data Structures: A stack stk is initialized as an empty list, which will store indices of bars. Two lists left and right are also initialized to store the left and right bounds for each bar (-1 for left and n for right, respectively, where n is the number of bars).

2. Traversing Heights: We loop through each bar using its index i and height h:

   • While the top of the stack is not empty and the current height h is less than or equal to the height at the index on top of the stack, we pop from the stack. This indicates that we have found a right boundary for the rectangle concerning the bar at the index that was just popped.

   • For each index we pop from the stack, we use it to set the corresponding right bound for that bar to the current index (i), since we now know this bar is taller than the current bar h.

   • If there are still elements left in the stack after popping, it indicates that the current bar h is larger than the bar at the top of the stack. Hence, the left boundary for the current bar h is now known to be the index on top of the stack.

   • Finally, we add the current index i to the top of the stack.

3. Calculating the Largest Area: Once the traversal is done, we have left and right arrays filled with the bounds of potential rectangles for each bar. To calculate the largest area:

   • Iterate over each index i and corresponding height h, and calculate the width for the largest rectangle that can be formed with height h by subtracting left[i] from right[i] and subtracting 1 (as the boundaries are exclusive).

   • Calculate the area for each rectangle by multiplying its height (heights[i]) with the width calculated above.

   • Use the max function to determine the largest area from these.

4. Return the Largest Area: After iteration, return the maximum area calculated, which is the area of the largest rectangle in the histogram.

The code snippet provided uses list comprehension at the end to perform the calculation of the areas and find the maximum all in one line, showcasing an efficient Pythonic approach:

return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))

This algorithm uses a stack efficiently that follows the Last-In-First-Out (LIFO) principle, whereby each element is pushed and popped only once, resulting in a time complexity of O(n) where n is the number of bars in the histogram.

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the heights array:

heights = [2, 1, 5, 6, 2, 3]

This represents a histogram with 6 bars where the heights of the bars are [2, 1, 5, 6, 2, 3].

1. Initializing Data Structures:

   stk = []
   left = [-1] * len(heights)
   right = [len(heights)] * len(heights)

2. Traversing Heights: We start traversing the heights array.

   • For heights[0], since the stack is empty, no action is taken other than pushing the index onto the stack:

     stk = [0]

   • For heights[1], the current height 1 is less than the height at the top of the stack 2. We pop from the stack (popping 0):

     stk = []

     We update right[0] = 1 and since stk is now empty, we push the current index 1 onto the stack:

     stk = [1]

   • For heights[2] (5), the stack action yields:

     stk = [1, 2]

   • For heights[3] (6):

     stk = [1, 2, 3]

   • For heights[4] (2), we start popping since 2 is less than 6 and 5. After popping 3 and 2:

     stk = [1]

     We update right[3] = 4, right[2] = 4. The stack still has 1 in it, so left[4] = 1. Push 4 onto the stack:

     stk = [1, 4]

   • For heights[5] (3):

     stk = [1, 4, 5]

3. Calculating the Largest Area:

   • We've completed the traversal, left = [-1, -1, 1, 2, 1, 4] and right = [1, 6, 4, 4, 6, 6].

   • Calculate the widths and areas for each bar; for example:

     • For i=2 (height = 5):

       width = right[2] - left[2] - 1 = 4 - 1 - 1 = 2

       area = heights[2] * width = 5 * 2 = 10

     • Repeat this for each bar and find the max area:

       areas = [2 * (1 - (-1) - 1), 1 * (6 - (-1) - 1), ... ]

       After evaluating all areas, the largest one is 10 (for heights[2]).

4. Return the Largest Area:

   • The maximum calculated area is 10, which is the area of the largest rectangle in the histogram we started with.

Solution Implementation

Time and Space Complexity

The time complexity of the largestRectangleArea function can be analyzed by looking at the operations performed inside the function.

• The function initializes three lists named left, right, and stk, and also iterates over the input heights list twice (once for populating the left and right lists, and once for calculating the maximum area). Each element of the heights list is processed exactly once during these iterations, leading to O(n) time for each loop.

• The stack stk is used to keep track of the indices of the rectangles in ascending order of their heights. For each element in heights, the stack may perform a push operation (stk.append(i)). Additionally, while the current height is less than or equal to the height of the rectangle corresponding to the index at the top of the stack, pop operations occur, and the right bound for the rectangle is updated. Despite this, each element is added to the stack once and removed from the stack at most once over the entire run of the loop, leading to a total of O(n) operations.

Based on these points, the overall time complexity of the largestRectangleArea function is O(n).

As for the space complexity:

• The extra space is used for the stk, left, and right lists, each of size n, where n is the number of elements in the input heights list. Thus, the space complexity is O(n), correlating with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.