MaiDeveloper

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.

largest-rectangle-in-histogram-figure-1
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

largest-rectangle-in-histogram-figure-2
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 [1]', () => {
    assert.strictEqual(largestRectangleArea([1]), 1);
  });

});

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

  3 passing (115ms)


Mike Mai
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.