How to find the max rectangular area in histogram

Let's assume that we are working with the following histogram and we want to calculate the area of the largest rectangle:

terminal

              8
          7 |---|
        |---|   |
        |   |   |
      4 |   |   |
  3 |---|   |   | 3
|---|   |   |   |---|
|   |   |   |   |   |
|   |   |   |   |   |
  0   1   2   3   4
  

For example, let's go to i = 1, h[i] = 4. At this point, the largest rectangle we can draw is:

terminal

              8
          7 |---|
        |---|   |
        |   |   |
      4 |   |   |
  3 |---|---|---| 3
|---|+++|+++|+++|---|
|   |+++|+++|+++|   |
|   |+++|+++|+++|   |
  0   1   2   3   4
      ↑       ↑
     Left   Right 


Area = (Right - Left + 1) * h[i] = (3 - 1 + 1) * 4 = 12
  

Now, let's go to i = 2, h[i] = 7. At this point, the largest rectangle we can draw is:

terminal

              8
          7 |---|
        |---|---|
        |+++|+++|
      4 |+++|+++|
  3 |---|+++|+++| 3
|---|   |+++|+++|---|
|   |   |+++|+++|   |
|   |   |+++|+++|   |
  0   1   2   3   4
          ↑   ↑
        Left Right 
     
Area = (Right - Left - 1) * h[i] = (3 - 2 + 1) * 7 = 14
  

Notice how the largest rectangle for a position i is always contained between the first two rectangles that are shorter than the one at position i.

We can find the right and left limits for each position and create the following array:

terminal
rectangles = [[0, 4], [1, 3], [2, 3], [3, 3], [0, 4]];

At this point, we can calculate the area of each rectangle:

terminal
areas = [[15], [12], [14], [8], [15]]

Largest rectangle area is 15.

How to code it

Our goals:

1. Obtain an array of rectangles with their right and left limits.
2. Iterate through the histogram just one time.

Let's write a skeleton:

javascript

function largestRectangle(h){

    // Defining max area
    let maxArea = 0;
    
    // Defining rectangles array to get right and left limit for each position
    let rectangles = [];
    
    // Defining incomplete rectangles stack
    let incomplete = [];
    
    // Iterating through histogram
    for(let i = 0; i < h.length; i ++){
        
        // When we read the height of a bar, we know the left limit
        // But we don't know the end of it
        rectangles[i] = [i, 'To be determined'];
        
        // As we don't know the right limit of the bar, we push it as incomplete
        incomplete.push(i);
    
    }

}

Now comes the tricky point. To be determined becomes numerical when the current bar is shorter than the previous one.

Example: i = 4, h = 3

terminal

              8
          7 |---|
        |---|   |
        |   |   |
      4 |   |   |
  3 |---|   |   | 3
|---|   |   |   |---|
|   |   |   |   |   |
|   |   |   |   |   |
  0   1   2   3   4
                  ↑
                We are here
                
rectangles = [[0, 'To be determined'], [1, 'To be determined'], [2, 'To be determined'], [3, 3], [4, 'To be determined']]
                                                                                             ↑
                                                                                            This point can be determined

But not only this point:

terminal

              8
          7 |---|
        |---|   |
        |   |   |
      4 |   |   |
  3 |---|   |   | 3
|---|   |   |   |---|
|   |   |   |   |   |
|   |   |   |   |   |
  0   1   2   3   4
                  ↑
                We are here
                
rectangles = [[0, 'To be determined'], [1, 3], [2, 3], [3, 3], [4, 'To be determined']]
                                           ↑        ↑       ↑
                                        These points can be determined

Finally:

terminal

              8
          7 |---|
        |---|   |
        |   |   |
      4 |   |   |
  3 |---|   |   | 3
|---|   |   |   |---|
|   |   |   |   |   |
|   |   |   |   |   |
  0   1   2   3   4
                  ↑
                We are here                                 This point can be extended to i = 1
                                                                ↓
rectangles = [[0, 'To be determined'], [1, 3], [2, 3], [3, 3], [1, 'To be determined']]
 

If we translate this behaviour into code:

javascript
function largestRectangle(h){

    // Defining max area
    let maxArea = 0;
    
    // Defining rectangles array to get right and left limit for each position
    let rectangles = [];
    
    // Defining incomplete rectangles stack
    let incomplete = [];
    
    // Iterating through histogram
    for(let i = 0; i < h.length; i ++){
        
        // When we read the height of a bar, we know the left limit
        // But we don't know the end of it
        rectangles[i] = [i, 'To be determined'];
        
        // Check if the current bar is smaller than the previous
        // In that case, determine points from incompleted rectangles
        while(i > 0 && h[i - 1] > h[i] && h[incomplete[incomplete.length - 1]] > h[i]){
            
            // We can get the last incompleted element
            let incompleted = incomplete.pop();
            
            // This points can be determined
            rectangles[incompleted] = [rectangles[incompleted][0], i - 1];
            
            // This point can be extended
            rectangles[i] = [incomplete.length > 0 ? incomplete[incomplete.length - 1] + 1 : 0, 'To be determined'];
            
        }
        
        // As we don't know the right limit of the bar, we push it as incomplete
        incomplete.push(i);
    
    }

}

At this point we'll have the array of rectangles, we can compute the max area as:

javascript
// Looping through array of rectangles
for(let i = 0; i < h.length; i ++){

    // Notice that remaining 'To be determined' values are now determined
    // Since we have iterated through the whole array
    let left   = rectangles[i][0];
    let right  = rectangles[i][1] === 'To be determined' ? h.length - 1 : rectangles[i][1];
    let height = h[i];

    // Here we can calculate new area
    let area = (right - left + 1) * height;

    // Defining maxArea
    if(area > maxArea) maxArea = area;

}

Note: This problem can be solved with O(N) time complexity. For simplicity in the explanation, the solution's time complexity is O(2N), but the same principles apply.