84. Largest Rectangle in Histogram (R)

Link: https://leetcode.com/problems/largest-rectangle-in-histogram

Description: Given an array of integers representing the histogram's bar height, find the area of the largest rectangle in the histogram.

Solution:

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
  let stack = [-1] // Initialize stack with -1 to help calculate width for the first bar
  let maxArea = 0

  for (let i = 0; i < heights.length; i++) {
    // Pop from stack and calculate area when the current bar is shorter than the stack's top bar
    while (stack.length > 1 && heights[i] <= heights[stack[stack.length - 1]]) {
      let height = heights[stack.pop()]
      let width = i - stack[stack.length - 1] - 1
      maxArea = Math.max(maxArea, height * width)
    }
    stack.push(i)
  }

  // Handle the remaining bars in the stack
  while (stack.length > 1) {
    let height = heights[stack.pop()]
    let width = heights.length - stack[stack.length - 1] - 1
    maxArea = Math.max(maxArea, height * width)
  }

  return maxArea
}

Explanaition:

Start: We're looking for the largest rectangle that can fit in the histogram.
For Each Bar: If a bar is shorter than the one before it, the previous taller bar's rectangle ends here. We calculate how large that rectangle was.
Track Potential Rectangles: We use a stack to keep track of which bars might still form larger rectangles.
End: Once we've considered every bar, we look at what's left in the stack (these bars extend to the end of the histogram) and calculate their areas too.
Result: The largest area we found during this process is our answer.

Line-by-Line Explanation:

The Setup:

var largestRectangleArea = function(heights) {
    let stack = [-1];
    let maxArea = 0;

We start by defining our function largestRectangleArea that takes heights as its input.
stack = [-1] is initialized with -1 to act as a marker for the start of the histogram. This makes it easier to calculate widths later.
maxArea is used to keep track of the largest rectangle area we've found so far.

Iterating Through Bars:

    for (let i = 0; i < heights.length; i++) {

We loop through each bar in the histogram using its index i.

Pop and Calculate Area When Necessary:

while (stack.length > 1 && heights[i] <= heights[stack[stack.length - 1]]) {
  let height = heights[stack.pop()]
  let width = i - stack[stack.length - 1] - 1
  maxArea = Math.max(maxArea, height * width)
}

Inside the loop, we check if the current bar (heights[i]) is shorter than the bar at the top of the stack. If so, it means the previous taller bar can't extend further right without being interrupted by the current shorter bar.
We then calculate the area of the rectangle that can be formed by the bar at the top of the stack. Its height is the value of that bar, and its width is the difference between the current index i and the index just before the top of the stack - this is how far to the left the rectangle can extend.
We update maxArea if this new area is larger than what we've found before.

Push the Current Index onto the Stack:

stack.push(i)

After handling the shorter bar scenario, or if the current bar is taller than the last one in the stack, we add the current index i to the stack. This is because the current bar now has potential to form part of a larger rectangle.

Handling Remaining Bars in the Stack:

while (stack.length > 1) {
  let height = heights[stack.pop()]
  let width = heights.length - stack[stack.length - 1] - 1
  maxArea = Math.max(maxArea, height * width)
}

After processing all bars, there might still be bars left in the stack. These bars did not find a shorter bar to their right, meaning they extend all the way to the end of the histogram.
We calculate the area for these remaining bars similarly, using the end of the histogram as their right boundary.

Return the Largest Area Found:

    return maxArea;
};

Finally, we return the largest rectangle area that we've found.

Explanation with Example:

Initial Setup:

heights = [2,1,5,6,2,3]
Initialize stack = [-1]. The -1 helps us handle the calculation of the width of the first rectangle.
maxArea = 0, to keep track of the largest rectangle found.

Walkthrough:

Start with the first bar (height = 2).
- stack = [-1, 0] (We push the index 0, not the height).
- No area calculation yet, as we need at least one more bar to form a rectangle.
Move to the second bar (height = 1).
- The current bar's height is less than the height of the top index in the stack (heights[0] = 2).
- Pop 0 from the stack. Calculate area with height 2 (from index 0) and width 1 - (-1) - 1 = 1. Area = 2 * 1 = 2.
- Update maxArea to 2.
- Push index 1 onto the stack, stack = [-1, 1].
Next, the third bar (height = 5).
- stack becomes [-1, 1, 2]. No popping because 5 is greater than 1.
Fourth bar (height = 6).
- stack becomes [-1, 1, 2, 3]. No popping because 6 is greater than 5.
Fifth bar (height = 2).
- Now, we have a bar shorter than the previous one. Start popping until we find a bar shorter than 2 or the stack is empty.
- Pop index 3 (height = 6). Area = 6 _ (4 - 2 - 1) = 6. New maxArea is 6.
- Pop index 2 (height = 5). Area = 5 _ (4 - 1 - 1) = 10. New maxArea is 10.
- Stop popping because the current bar's height is greater than the height at the top of the stack (index 1, height = 1).
- stack now is [-1, 1, 4].
Last bar (height = 3).
- Push index 5 onto the stack, stack = [-1, 1, 4, 5]. No popping because 3 is greater than 2.

Finishing Up

Now we've processed all bars. We need to clear the stack:
- Pop index 5 (height = 3). Area = 3 _ (6 - 4 - 1) = 3. maxArea remains 10.
- Pop index 4 (height = 2). Area = 2 _ (6 - 1 - 1) = 8. maxArea remains 10.
- Pop index 1 (height = 1). Area = 1 * (6 - (-1) - 1) = 6. maxArea remains 10.
The stack is now back to just [-1], and we've found the maximum area to be 10, which corresponds to the rectangle formed by bars at indices 2 and 3 (heights 5 and 6) with a width of 2 units.