# My straightforward Java O(n) solution

• public class Solution {

// 1. find the max value index in height array

// 2. sum up the water of each bin contains in the left side of max height from index 0.

// 3. sum up the water of each bin contains in the right side of max height from index height.length - 1.

``````public int trap(int[] height) {
if(height == null || height.length <= 1){
return 0;
}
int sum = 0;
int index = 0;
for(int i = 0; i < height.length; i++){
if(height[i] > height[index]){
index = i;
}
}

int pre = -1;
int i = 0;
while(i < index){
if(height[i] < pre){
sum += (pre - height[i]);
}
else{
pre = height[i];
}
i++;
}

i = height.length - 1;
pre = -1;
while(i > index){
if(height[i] < pre){
sum += (pre - height[i]);
}
else{
pre = height[i];
}
i--;
}
return sum;
}
``````

// This solution is easy to understand, but a better solution is to scan the array only once starting from both side.
}

• So smart. It's nearly a one-pass solution!

• thanks........ .

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