2

In LeetCode problem #84, "Largest Rectangle in Histogram", we're given a bar graph in the form int[] heights, and we need to find and return the area of the "largest rectangle" in the bar graph, meaning the maximum possible value of (j - i + 1) * min(heights[i], heights[i+1], ..., heights[j-1], heights[j]) (by choosing i and j appropriately).

Apparently the below solution gives average-case time complexity in O(n log n), worst-case time complexity in O(n2), and space complexity in O(n). Why is that? I'm particularly perplexed about how to think about it so that O(n log n) makes sense.

public class Solution {
    public int calculateArea(int[] heights, int start, int end) {
        if (start > end)
            return 0;
        int minindex = start;
        for (int i = start; i <= end; i++) {
            if (heights[minindex] > heights[i]) {
                minindex = i;
            }
        }
        return Math.max(
            heights[minindex] * (end - start + 1),
            Math.max(
                calculateArea(heights, start, minindex - 1),
                calculateArea(heights, minindex + 1, end)));
    }

    public int largestRectangleArea(int[] heights) {
        return calculateArea(heights, 0, heights.length - 1);
    }
}
ruakh
  • 175,680
  • 26
  • 273
  • 307
Shisui
  • 1,051
  • 1
  • 8
  • 23
  • 2
    The space complexity is O(n) because you have to factor in the stack space in recursive calls. "When you make a recursive call the cpu needs to remember where to continue execution of your program so the state is saved and a copy of your function push on the stack" – cheesey Sep 03 '20 at 03:04
  • 1
    Regarding the time complexity: the algorithm seems to follow a "divide and conquer" strategy, so I imagine the average-case analysis would be similar to [the one for Quicksort](https://en.wikipedia.org/wiki/Quicksort#Average-case_analysis). Perhaps someone else can provide a formal proof, I'm not that skilled I'm afraid. – Kevin K Sep 03 '20 at 03:38
  • "why the average case time complexity is O(nlog(n)), the worst case O(n2) and the space requirement being O(n)?" Well, what do you think the values *should* be? What is your reasoning? – Karl Knechtel Sep 05 '20 at 17:27

0 Answers0