Very Concise Java Solution No Stack with Explanations


  • 34
    M

    The idea is very simple. Begin scan from beginning and end of array. Compare value of left and right pointer, hold the greater one and move the other to inner array. Compute passed area when pointer gets inner.

    public int trap(int[] height) {
    	int secHight = 0;
    	int left = 0;
    	int right = height.length - 1;
    	int area = 0;
    	while (left < right) {
    		if (height[left] < height[right]) {
    			secHight = Math.max(height[left], secHight);
    			area += secHight - height[left];
    			left++;
    		} else {
    			secHight = Math.max(height[right], secHight);
    			area += secHight - height[right];
    			right--;
    		}
    	}
    	return area;
    }

Log in to reply
 

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