5ms O(n) Java solution explained (beats 96%)


  • 50
    A

    For any bar i the maximum rectangle is of width r - l - 1 where r - is the last coordinate of the bar to the right with height h[r] >= h[i] and l - is the last coordinate of the bar to the left which height h[l] >= h[i]

    So if for any i coordinate we know his utmost higher (or of the same height) neighbors to the right and to the left, we can easily find the largest rectangle:

    int maxArea = 0;
    for (int i = 0; i < height.length; i++) {
        maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
    }
    

    The main trick is how to effectively calculate lessFromRight and lessFromLeft arrays. The trivial solution is to use O(n^2) solution and for each i element first find his left/right heighbour in the second inner loop just iterating back or forward:

    for (int i = 1; i < height.length; i++) {              
        int p = i - 1;
        while (p >= 0 && height[p] >= height[i]) {
            p--;
        }
        lessFromLeft[i] = p;              
    }
    

    The only line change shifts this algorithm from O(n^2) to O(n) complexity: we don't need to rescan each item to the left - we can reuse results of previous calculations and "jump" through indices in quick manner:

    while (p >= 0 && height[p] >= height[i]) {
          p = lessFromLeft[p];
    }
    

    Here is the whole solution:

    public static int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int[] lessFromLeft = new int[height.length]; // idx of the first bar the left that is lower than current
        int[] lessFromRight = new int[height.length]; // idx of the first bar the right that is lower than current
        lessFromRight[height.length - 1] = height.length;
        lessFromLeft[0] = -1;
    
        for (int i = 1; i < height.length; i++) {
            int p = i - 1;
    
            while (p >= 0 && height[p] >= height[i]) {
                p = lessFromLeft[p];
            }
            lessFromLeft[i] = p;
        }
    
        for (int i = height.length - 2; i >= 0; i--) {
            int p = i + 1;
    
            while (p < height.length && height[p] >= height[i]) {
                p = lessFromRight[p];
            }
            lessFromRight[i] = p;
        }
    
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
        }
    
        return maxArea;
    }

  • 7
    J

    The classic stack solution is simpler. However, using collection will be slower. Here is an implementation using int array to simulation a stack. The run time is 5 ms.

    public class Solution {
        public int largestRectangleArea(int[] h) {
            int n = h.length;
            int max = 0;
            int[] stack = new int[n + 1];
            int is = -1;
            for (int i = 0; i <= n; i++) {
                int height = (i == n) ? 0 : h[i];
                while (is != -1 && height < h[stack[is]]) {
                    int hh = h[stack[is--]];
                    int width = (is == -1) ? i : i - 1 - stack[is];
                    max = Math.max(max, hh * width);
                }
                stack[++is] = i;
            }
            return max;
        }
    }

  • 4
    W

    even you use p = lessFromLeft[p]; to jump quickly, I still do not think it is O(n) for the whole lessFromLeft array.


  • 0
    Y

    really nice solution


  • 2
    G

    @weihui Me too. I think it's still overall O(n^2) for worst case ([1,2,3,4,5,6,7...]). But the solution is great idea!


  • 3
    U

    @gtx108 This is still a O(N) solution. Try to compare it with Stack based solution. Both of these solutions are working in a similar manner but implemented in a different way. I hope @anton4 will second me.


  • 0
    C
    This post is deleted!

  • 0
    R

    @ufarooqi Could you explain more? Just like @gtx108 mentioned, worst case ([1,2,3,4,5,6,7...]) for lessFromLeft would be O(N^2), right?


  • 0
    A

    @River3 If we look attentively to the case, when it checks if the element from left is smaller than current element, it doesn't make a loop and steps into if. Therefore, it takes only O(n).
    A bit like KMP algo's implementation.


  • 0
    R

    @aybekko97 Say the previous result is [1,2,3,4,5,6,7], now given current element 0. then from 7 we jump to 6, then jump to 5, to 4, 3, 2, 1. Still need to compare N time for a single element right?


  • 3
    A

    @River3 Let's assume the array lessFromLeft calculated until now is [0,0,1,2,3,4,5] and heights array is [1,2,3,4,5,6,7,curr->1], yep it will loop until the element with index 0, but it makes this loop once for some range. Try to think on this example: [1,2,3,4,5,6,7,1,2,3,4,5,6,7] one loop from 7th to 0th elem., and from 14th to 7th. Then, if we sum these ranges it gives us O(n).


  • 0
    R

    @aybekko97 I think I get it. So it's amortized O(N).
    Thank you for your explanation!


  • 0
    L

    This by average is O(N) thanks to the quick jump.
    I use a similar idea, and it is pretty fast.


  • 0
    J

    The while loop runs at most 2N times, so its worst case O(N)


  • 0
    Y
    This post is deleted!

  • 0
    D

    The setting of lessFromLeft and lessFromRight loops in a triangular series per index which gives this solution an overall runtime of O(n^2). The advantage of a stack-based approach is that you can skip over indexes that you've already processed which gives even the worst case of O(n). For example here's my solution:

    class Solution {
         public int largestRectangleArea(int[] heights) {
    
            Deque<Integer> stack = new ArrayDeque<>(heights.length);
            int last_h = 0;
            int max = 0;
    
            for (int i = 0; i <= heights.length; i++) {
                int height = i == heights.length ? 0 : heights[i];
    
                if (height < last_h) {
                    int j = stack.peekLast();
                    int prev_j = j;
                    int prev_h = heights[j];
                    while (prev_h > height) {
                        prev_j = j;
                        stack.removeLast();
                        int area = prev_h * (i - j);
                        max = Math.max(max, area);
                        if (stack.isEmpty()) {
                            break;
                        }
                        
                        j = stack.peekLast();
                        prev_h = heights[j];
                    }
    
                    heights[prev_j] = height;
                    stack.addLast(prev_j);
    
                } else {
                    stack.addLast(i);
                }
    
                last_h = height;
    
            }
    
            return max;
         }        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.