My solution: O(1) space, 2 array iterations, Java


  • 1
    D

    First we find the max value overall. Then we know that for all left towers this will be the highest tower to the right, and for all right towers this will be the highest tower to the left. Then we process each half separately, from two sides, maintaining found max value.

    public int trap(int[] A) {
        int answer = 0;
        
        if (A.length <= 2) {
            answer = 0;
        }
        else {
            int maxValue = 0;
            int maxValueIndex = 0;
            
            for (int i = 0; i < A.length; i++) {
                int elem = A[i];
                if (elem > maxValue) {
                    maxValue = elem;
                    maxValueIndex = i;
                }
            }
            
            int totalDrops = 0;
            int leftMax = 0;
            
            for (int i = 0; i < maxValueIndex; i++) {
                int elem = A[i];
                if (elem > leftMax) {
                    leftMax = elem;
                }
                else {
                    totalDrops += leftMax - A[i];
                }
            }
            
            int rightMax = 0;
            
            for (int i = A.length - 1; i > maxValueIndex; i--) {
                int elem = A[i];
                if (elem > rightMax) {
                    rightMax = elem;
                }
                else {
                    totalDrops += rightMax - A[i];
                }
            }
            
            answer = totalDrops;
        }
        
        return answer;
    }

Log in to reply
 

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