Explanatory and concise java implementation.


  • 10

    Key idea is to keep a track of the highest walls on the left and the right and narrowing down from both sides. As we narrow down keeping adding to the result, the water trapped in unit width and smaller of each walls on each move.

    public class Solution {
        public int trap(int[] height) {
            if(height == null || height.length == 0) return 0;
            int leftMax = 0, rightMax = 0, waterTrapped = 0, left = 0, right = height.length-1;
            while(left < right) {
                leftMax = leftMax > height[left] ? leftMax : height[left];
                rightMax = rightMax > height[right] ? rightMax : height[right];
                waterTrapped += leftMax < rightMax ? leftMax - height[left++] : rightMax - height[right--];
            }
            return waterTrapped;
        }
    }

  • 0
    C

    Edited: nvm, I figured it out. :)


    Can you please give more explanation about leftMax < rightMax ? leftMax - height[left++] : rightMax - height[right--]?

    How did you come up with the decision that if leftMax < rightMax, move left, otherwise move right? I don't understand why this movement is always correct (and it is indeed).

    Thanks!


Log in to reply
 

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