Java divide and conquer approach O(nlogn) without using segment tree, 8mm beat 94%


  • 1
    S

    http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/

    See above for an easy to understand but relatively hard to implement solution using Divide and Conquer and segment tree.

    Instead of looking for the min using segment tree to split the main problem into two smaller problems, we can just split using the middle bar of the main problem.

    Then

    max_area of heights[left:right] = max_area[left:middle-1] + max_area[middle+1:right] + max_area of any rectangular containing the middle bar, where middle = (left + right)/2, as usual

    Time complexity: T(n) = 2T(n/2) + O(n) ----> O(n logn)

    Base case when problem size is either 1 or 2.
    To compute the max_area of any rectangular containing the middle bar. We maintain a min_level (which is just the height of current rectangle) initially set to be heights[i]. We also need a left boundary pointer and right boundary pointer that expand from middle.

    Whenever the the pointers see heights higher than min_level, we could keep expanding. When any pointer sees a lower height, we can no longer expand using the current min_level thus we compute the current rectangle area and then lower the min_level to be the new height. Be careful with all boundary conditions

    public class Solution {
        // Java program to find maximum rectangular area using Divide and Conquer O(nlogn)
        public int largestRectangleArea(int[] heights) {
            if(heights == null || heights.length == 0)  return 0;
            return largestRectangleArea(heights, 0, heights.length-1);
        }
        
        private int largestRectangleArea(int[] heights, int start, int end){
            if(start == end)   return heights[start];                          //base case
            if(start+1 == end){
                int min = (heights[start] < heights[end])? heights[start] : heights[end];
                return Math.max(2*min, heights[start]+heights[end]-min);
            }
            //divide
            int middle = start + (end - start)/2;
            int maxLeft = largestRectangleArea(heights, start, middle-1);       
            int maxRight = largestRectangleArea(heights, middle+1, end);
            //compute max area containing heights[middle];
            int maxMiddle = 0;
            int curMax;
            int l_ptr = middle - 1;
            int r_ptr = middle + 1;
            int min_level = heights[middle];
            while(l_ptr >= start || r_ptr <= end) {
                while(l_ptr >= start && heights[l_ptr] >= min_level)        l_ptr--;
                while(r_ptr <= end && heights[r_ptr] >= min_level)          r_ptr++;
                curMax = min_level * (r_ptr - l_ptr - 1);
                if(curMax > maxMiddle)      maxMiddle = curMax;            
                if(l_ptr >= start && r_ptr <= end) 
                    min_level = Math.max(heights[l_ptr], heights[r_ptr]);
                else if(l_ptr < start && r_ptr <= end)
                    min_level = heights[r_ptr];
                else if(l_ptr >= start && r_ptr > end)
                    min_level = heights[l_ptr];
                else
                    break;
            }
            return Math.max(maxMiddle, Math.max(maxLeft, maxRight));
        }
    }

Log in to reply
 

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