Java accepts solution O(n)


  • 0
    S

    The idea is, to first scan the heights to figure out the maximum height after each index => O(n)

    The second scan is to add the volume of the water for each column until it hits the wall then which it figures out a new wall size based on the max height after i. => O(n)

    public class Solution {
        public int trap(int[] height) {
            int n = height.length;
            if (n <= 2) return 0;
            
            // maxHeightsAfter[i]: the max height[j] s.t. j > i
            int []maxHeightsAfter = new int[n];
            maxHeightsAfter[n-1] = 0;
            for (int i = n-2; i >= 0; i--) {
                maxHeightsAfter[i] = Math.max(maxHeightsAfter[i + 1], height[i+1]);
            }
            
            // move to the first wall
            int i = 0;
            while (i < n && height[i] == 0) i++;
            
            int trapped = 0;
            boolean isNewWell = true;
            int maxHeightAfter = 0;
            int wall = 0;
            for (; i < n; i++) {
    	        if (!isNewWell) {
    	            trapped += Math.max(0, wall - height[i]);
    	            
    	            // end of the current well
    	            if (height[i] >= wall)
    	                isNewWell = true;
    	        }
            	
                // start of a new well (or a bowl)
                if (isNewWell) {
                    maxHeightAfter = maxHeightsAfter[i];
                    // no more walls after i
                    if (maxHeightAfter == 0) break;
                    
                    wall = Math.min(height[i], maxHeightAfter);
                    isNewWell = false;
                }
            }
            
            return trapped;
        }
    }

Log in to reply
 

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