# 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.

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