Java O(n) left/right arrays solution, 4ms beats 96%


  • 13
    R

    Basically, you run 3 passes:

    1. Scan from left to right to compute left[], which represents the left most boundary of current height.

    2. Scan from right to left to compute right[], which represents the right most boundary of current height.

    3. Scan from left to right again to compute rectangle area based on the height of that each position.


    public class Solution {
        public int largestRectangleArea(int[] heights) {
            // validate input
            if(heights == null || heights.length == 0) {
                return 0;
            }
            
            // init
            int n = heights.length;
            int[] left = new int[n];
            int[] right = new int[n];
            int result = 0;
            
            // build left
            left[0] = 0;
            for(int i = 1; i < n; i++) {
                int currentLeft = i-1;
                while(currentLeft >= 0 && heights[currentLeft] >= heights[i]) {
                    currentLeft = left[currentLeft]-1;
                }
                    
                left[i] = currentLeft+1;
            }
            
            // build right
            right[n-1] = n-1;
            for(int i = n-2; i >= 0; i--) {
                int currentRight = i+1;
                while(currentRight < n && heights[i] <= heights[currentRight]) {
                    currentRight = right[currentRight]+1;
                }
                    
                right[i] = currentRight-1;
            }
            
            // compare height
            for(int i = 0; i < n; i++) {
                result = Math.max(result, (right[i]-left[i]+1)*heights[i]);
            }
            
            // return
            return result;
        }
    }

  • 0
    L

    why not

    left[0] = 0;
    for(int i = 1; i < n; i++) {
        left[i] = (height[i] > height[left[i - 1]]) ? i : left[i - 1];
    }
    

    update : I see. Your are trying to find the element as left as possible, right?


  • 0
    C

    Genius idea. Something like dynamic programming. Store the left bound and right bound in the array. Greate implementation.


  • 1
    Y

    You sure it is O(n)?
    what about an ascending array or descending?


Log in to reply
 

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