Recursion, Divide & Conquer.


  • 1

    #1.
    Recursion, Divide & Conquer.
    find the tallest and 2nd tallest, call how much water could we trap between them. Then use the same method to calc the left and right part to it.

    public class Solution {
        public int trap(int[] height) {
            return trap(height, 0, height.length - 1);
        }
    
        public int trap(int[] height, int start, int end) {
            if(Math.abs(start - end) <= 1) { return 0; }
            int tallest = -1;
            int secondTall = -1;
            int idxTallest = -1;
            int idxSecondTall = -1;
            
            // find the index of the tallest
            for(int i = start; i <= end; i++) {
                if(height[i] > tallest) {
                    tallest = height[i];
                    idxTallest = i;
                }
            }
            //find the index of the 2nd tallest
            for(int i = start; i <= end; i++) {
                if(i != idxTallest && height[i] > secondTall){
                    secondTall = height[i];
                    idxSecondTall = i;
                }
            }
            
            //calc how much rain could we trap between tallest and 2nd tallest.
            int minIdx = Math.min(idxTallest, idxSecondTall);
            int maxIdx = Math.max(idxTallest, idxSecondTall);
            int trapped = secondTall * (Math.abs(idxTallest - idxSecondTall) -1);
            for(int i = minIdx + 1; i < maxIdx; i++){
                trapped -= height[i];
            }
            
            return trapped + trap(height, start, minIdx) + trap(height, maxIdx, end);
        }
    }
    

    #2
    2 pointers. 1 point to the left, from beginning and goes to right; the other point to the right and goes to left. The logic might looks like "merging 2 sorted list", but it's different. The difference is we need to calculate the water it could contain from bottom (floor) to up. At first we need to imagine each bar could also contain water, and then reduce them from the result.
    for example:
    [1, 0, 2, 1, 0, 2] -- value;
    {0, 1, 2, 3, 4, 5} -- index;
    for the 1st layer from bottom to up, the height is 1, the length is 6, (5 - 0 + 1).
    for the 2nd layer from bottom (the last max height, which is 1) to up, the height is 1 (from 2 - last max height of 1), the length is 4, (5 - 2 + 1). Then the sum is 10. and remove the sum of heights since they were counted into the value. The it's done.

    public class Solution {
        /**
         * @param heights: an array of integers
         * @return: a integer
         */
        public int trap(int[] heights) {
            // write your code here
            if(heights == null || heights.length == 0) {
                return 0;
            }
            int left =  0;
            int right = heights.length - 1;
            int sum = 0;
            int currMaxHeight = 0;
            while(left <= right) {
                int hLeft = heights[left];
                int hRight = heights[right];
                if(hLeft <= hRight) {
                    if(hLeft > currMaxHeight) {
                        sum += (right - left + 1) * (hLeft - currMaxHeight); // length * height.
                        currMaxHeight = hLeft;
                    }
                    left++;
                } else {
                    if(hRight > currMaxHeight){
                        sum += (right - left + 1) * (hRight - currMaxHeight); //length * height
                        currMaxHeight = hRight;
                    }
                    right--;
                }
            }
            for(int h : heights) {
                sum -= h;
            }
            return sum;
        }
    }
    

  • 0
    Z

    very clever and easy-understand solution


  • 0

    thanks for the upvote.
    I found I could find the tallest and second tallest in a single 'for' loop. It would look like

    public class Solution {
        public int trap(int[] height) {
            return trap(height, 0, height.length - 1);
        }
        
        public int trap(int[] height, int start, int end) {
            if(Math.abs(start - end) <= 1) { return 0; }
            int tallest = -1;
            int secondTall = -1;
            int idxTallest = -1;
            int idxSecondTall = -1;
            // find the index of the tallest
            for(int i = start; i <= end; i++) {
                if(height[i] > tallest) {
                    secondTall = tallest;
                    idxSecondTall = idxTallest; 
                    tallest = height[i];
                    idxTallest = i;
                } else if(height[i] > secondTall) {
                    secondTall = height[i];
                    idxSecondTall = i; 
                }
            }
            //calc how much rain could we trap between tallest and 2nd tallest.
            int minIdx = Math.min(idxTallest, idxSecondTall);
            int maxIdx = Math.max(idxTallest, idxSecondTall);
            int trapped = secondTall * (Math.abs(idxTallest - idxSecondTall) -1);
            for(int i = minIdx + 1; i < maxIdx; i++){
                trapped -= height[i];
            }
            return trapped + trap(height, start, minIdx) + trap(height, maxIdx, end);
        }
    }
    

  • 0
    Z
    This post is deleted!

  • 0
    Z

    Is the time complexity O(n)?


  • 0

    @zfrancica I think the average case would be O(n*log(n)), the worst case would be O(n^2). I really hope it could be O(n), do you know anybody made an O(n) solution? thanks


Log in to reply
 

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