# Largest Rectangle in Histogram in JavaScript

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest rectangle is shown in the filled area, which has area = 10 unit.

``````Example:

Input: [2,1,5,6,2,3]
Output: 10
``````

## Solution

``````
/**
* Get the largest rectangle area
* @param {number[]} heights
* @return {number}
* @time complexity: O(n)
* @space complexity: O(n)
*/
const largestRectangleArea = heights => {

const n = heights.length,
stack = [];

let maxArea = 0;

for (let i = 0; i < n; i++) {

// Check if the current bar is lower than the previous bar in the stack
while (stack.length && heights[i] <= heights[stack[stack.length-1]]) {
// Calculate the area
maxArea = Math.max(maxArea, getArea(i, heights, stack));
}

stack.push(i);
}

// Calcualte the remaining bar in the stack
while (stack.length) {
maxArea = Math.max(maxArea, getArea(n, heights, stack));
}

return maxArea;
};

/**
* Calcualte the area
* @param {number} i          index element in heights
* @param {number[]} heights
* @param {number[]} stack
* @return {number}
* @time complexity: O(1)
* @space complexity: O(1)
*/
const getArea = (i, heights, stack) => {
const h = heights[stack.pop()],
w = stack.length ? i - stack[stack.length-1] - 1 : i;

return h * w;
};
```
```

## Test Cast

``````
import { assert } from 'chai';

describe('Largest Rectangle in Histogram', () => {

it('should find the longest path', () => {
assert.strictEqual(largestRectangleArea([2,1,5,6,2,3]), 10);
});

it('should return 2 for [1, 1]', () => {
assert.strictEqual(largestRectangleArea([1, 1]), 2);
});

it('should return 1 for ', () => {
assert.strictEqual(largestRectangleArea(), 1);
});

});
```
```
``````  Largest Rectangle in Histogram
✓ should find the longest path
✓ should return 2 for [1, 1]
✓ should return 1 for 

3 passing (115ms)
`````` Mike Mai   Brooklyn, New York
I am full-stack web developer, passionate about building world class web applications. Knowledge in designing, coding, testing, and debugging. I love to solve problems.