# Java solution with comments, O(n) time

• ``````public class Solutions {
public int trap(int[] height) {
// corner case
if (height == null || height.length < 3) return 0;
// hi is the index of the highest pole
int total = 0, hi = 0;
// first thing is to find the highest's index
for (int i = 1; i < height.length; i++) {
if (height[i] > height[hi]) {
hi = i;
}
}
// each round we start from a pole and find the next one that is equal or higher than it
// it's guaranteed that there must be at least one pole >= current pole before (include) the highest pole
// records the obstacles between those two poles so we will subtract that part
int cur = 0, next = 0, obstacle = 0;
while (cur != hi) {// loop util cur reached hi (left -> right)
next = cur + 1;
while (height[cur] > height[next]) { // loop until we find the next pole >= cur pole
obstacle += height[next]; // records the obstacles
next++;
}
// now, next pole is equal or larger than cur, we can add some to total
total += (next - cur - 1) * height[cur] - obstacle; // do not forget to - 1
obstacle = 0;
cur = next; // start next round, current pole should be the one we found last round
}

// do it from right -> left
cur = height.length - 1;
while (cur != hi) {
next = cur - 1;
while (height[cur] > height[next]) {
obstacle += height[next];
next--;
}
total += (cur - next - 1) * height[cur] - obstacle;
obstacle = 0;
cur = next;
}
// finished