Easy O(n) solution, one pass


  • 0
    T
    public class Solution {
        public int trap(int[] height) {
            int water;
            int lowest = 0;
            int left = 0;
            int right = height.length - 1;
            int lower = 0;
            while(left < right){
                water += Math.max(0, lowest - height[left]);
                water += Math.max(0, lowest - height[right]);
                lower = Math.min(height[right], height[left]);
                lowest = Math.max(lowest, lower);
                if(height[left] <= height[right]) left++;
                else right--;
            }
            return water;
        }
    }
    

Log in to reply
 

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