# Java accepts solution O(n)

• The idea is, to first scan the heights to figure out the maximum height after each index => O(n)

The second scan is to add the volume of the water for each column until it hits the wall then which it figures out a new wall size based on the max height after i. => O(n)

``````public class Solution {
public int trap(int[] height) {
int n = height.length;
if (n <= 2) return 0;

// maxHeightsAfter[i]: the max height[j] s.t. j > i
int []maxHeightsAfter = new int[n];
maxHeightsAfter[n-1] = 0;
for (int i = n-2; i >= 0; i--) {
maxHeightsAfter[i] = Math.max(maxHeightsAfter[i + 1], height[i+1]);
}

// move to the first wall
int i = 0;
while (i < n && height[i] == 0) i++;

int trapped = 0;
boolean isNewWell = true;
int maxHeightAfter = 0;
int wall = 0;
for (; i < n; i++) {
if (!isNewWell) {
trapped += Math.max(0, wall - height[i]);

// end of the current well
if (height[i] >= wall)
isNewWell = true;
}

// start of a new well (or a bowl)
if (isNewWell) {
maxHeightAfter = maxHeightsAfter[i];
// no more walls after i
if (maxHeightAfter == 0) break;

wall = Math.min(height[i], maxHeightAfter);
isNewWell = false;
}
}

return trapped;
}
}``````

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