0084-largest-rectangle-in-histogram.js

/**
 * https://leetcode.com/problems/largest-rectangle-in-histogram/solution/
 * Time O(N^3) | Space O(1)
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights, maxArea = 0) {
    for (let i = 0; i < heights.length; i++) {
        /* Time O(N) */
        for (let j = i; j < heights.length; j++) {
            /* Time O(N) */
            let min = Infinity;

            for (let k = i; k <= j; k++) {
                /* Time O(N) */
                min = Math.min(min, heights[k]);
            }

            const area = min * (j - i + 1);

            maxArea = Math.max(maxArea, area);
        }
    }

    return maxArea;
};

/**
 * https://leetcode.com/problems/largest-rectangle-in-histogram/solution/
 * Time O(N^2) | Space O(1)
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights, maxArea = 0) {
    for (let i = 0; i < heights.length; i++) {
        /* Time O(N) */
        let min = Infinity;

        for (let j = i; j < heights.length; j++) {
            /* Time O(N) */
            min = Math.min(min, heights[j]);

            const area = min * (j - i + 1);

            maxArea = Math.max(maxArea, area);
        }
    }

    return maxArea;
};

/**
 * https://leetcode.com/problems/largest-rectangle-in-histogram/solution/
 * Time O(N^2) | Space O(N)
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (
    heights,
    left = 0,
    right = heights.length - 1,
) {
    const isBaseCase = right < left;
    if (isBaseCase) return 0;

    return divideAndConquer(
        heights,
        left,
        right,
    ); /* Time O(N^2) | Space O(N) */
};

const divideAndConquer = (heights, left, right, min = left) => {
    for (let i = left; i <= right; i++) {
        /* Time O(N) */
        const isMinGreater = heights[i] < heights[min];
        if (!isMinGreater) continue;

        min = i;
    }

    const window = right - left + 1;
    const area = heights[min] * window;

    const leftArea = largestRectangleArea(
        heights,
        min + 1,
        right,
    ); /* Time O(N^2) | Space O(N) */
    const rightArea = largestRectangleArea(
        heights,
        left,
        min - 1,
    ); /* Time O(N^2) | Space O(N) */

    return Math.max(area, leftArea, rightArea);
};

/**
 * https://leetcode.com/problems/largest-rectangle-in-histogram/solution/
 * Time O(N) | Space O(N)
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
    const { stack, maxArea } = fillStack(heights); /* Time O(N) | Space O(N) */

    return getMaxArea(heights, stack, maxArea); /* Time O(N) */
};

const fillStack = (heights, stack = [], maxArea = 0) => {
    for (let index = 0; index < heights.length; index++) {
        /* Time O(N + N) */
        let start = index;

        const isCurrHeightLess = ([prevIndex, prevHeight], currHeight) =>
            currHeight < prevHeight;
        const canShrink = () =>
            isCurrHeightLess(stack[stack.length - 1], heights[index]);
        while (stack.length && canShrink()) {
            /* Time O(N + N) */
            const [_index, _height] = stack.pop();
            const width = index - _index;
            const area = _height * width;

            maxArea = Math.max(maxArea, area);
            start = _index;
        }

        stack.push([start, heights[index]]); /* Space O(N) */
    }

    return { stack, maxArea };
};

const getMaxArea = (heights, stack, maxArea) => {
    for (const [index, height] of stack) {
        /* Time O(N) */
        const width = heights.length - index;
        const area = height * width;

        maxArea = Math.max(maxArea, area);
    }

    return maxArea;
};