My Java O(1) space, O(n) time solution


  • 1
    Y
    public class Solution {
        public int trap(int[] height) {
            if(height.length <= 2) return 0;
            int max = 0;
            int highestIndex = 0, total = 0;
            for(int i = 0; i < height.length; i++) {
            	if(height[highestIndex] < height[i]) 
            		highestIndex = i;
            	total += height[i];
            }
            
            int left = 0;
            int curr = 0;
            while(left < highestIndex) {
            	if(height[curr] < height[left]) 
            		curr = left;
            	max = max + height[curr];
            	left++;
            }
            
             int right = height.length - 1;
            curr = height.length -1;
            while(right > highestIndex) {
            	if(height[curr] < height[right]) 
            		curr = right;
            	max = max + height[curr];
            	right--;
            }
             
            return max + height[highestIndex]- total;
        }
    }

  • 0
    A

    can you explain the logic


Log in to reply
 

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