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.

Our goals:

- Obtain an array of rectangles with their right and left limits.
- 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.

Hi, I'm Erik, an engineer from Barcelona. If you like the post or have any comments, say hi.