Largest Rectangle in Histogram (https://leetcode.com/problems/largest-rectangle-in-histogram)

largest-rectangle-in-histogram.js

// Time: O(n * log (n))
// Memory: O(log (n))

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    if (!heights.length) {
        return 0;
    }
    return maxArea(heights, 0, heights.length - 1);
};

function maxArea(arr, left, right) {
    if (left > right) {
        return 0;
    }
    if (left === right) {
        return arr[left];
    }
    const min = indexOfMin(arr, left, right);
    const leftMax = maxArea(arr, left, min - 1);
    const rightMax = maxArea(arr, min + 1, right);
    
    return Math.max(leftMax, rightMax, arr[min] * (right - left + 1));
}

function indexOfMin(arr, left, right) {
    let min = left;
    
    for (let i = left + 1; i <= right; i++) {
        if (arr[i] < arr[min]) {
            min = i;
        }
    }
    return min;
}

It's not O(n * log n), it's n^2