# Java O(n) accepted solution

• Steps:

1. Find all valleys
2. Merge these valleys based on their edge heights
3. Calculate the amount of water each valley can contain
class Solution {
public int trap(int[] height) {
if (height.length <= 1) {
return 0;
}

int result = 0;

List<int[]> endpoints = findEndpoints(height);
List<int[]> mergedEndpoints = mergeEndpoints(endpoints, height);

for (int[] eps : mergedEndpoints) {
int start = eps[0];
int end = eps[1];

int edgeHeight = Math.min(height[start], height[end]);
int currResult = edgeHeight * (end - start + 1);
for (int j = start; j <= end; j++) {
currResult -= Math.min(height[j], edgeHeight);
}

result += currResult;
}

return result;
}

private List<int[]> findEndpoints(int[] height) {
List<int[]> result = new ArrayList<>();

boolean isInclining = height[1] > height[0];
int trapStartIndex = height[1] < height[0] ? 0 : -1;

for (int i = 1; i < height.length; i++) {
if (height[i] == height[i - 1]) {
if (trapStartIndex != -1 && i == height.length - 1) {
result.add(new int[] { trapStartIndex, i });
}

continue;
}

if (height[i] > height[i - 1]) {
isInclining = true;

if (trapStartIndex == -1) {
continue;
}

if (isInclining) {
if (i == height.length - 1) {
result.add(new int[] { trapStartIndex, i });
trapStartIndex = -1;
}
}
} else {
if (trapStartIndex == -1) {
isInclining = false;
trapStartIndex = i - 1;

if (i == height.length - 1) {
result.add(new int[] { trapStartIndex, i });
}
} else {
if (isInclining) {
isInclining = false;
result.add(new int[] { trapStartIndex, i - 1 });
trapStartIndex = i - 1;
}

if (i == height.length - 1) {
result.add(new int[] { trapStartIndex, i });
}
}
}
}

return result;
}

private List<int[]> mergeEndpoints(List<int[]> endpoints, int[] height) {
List<int[]> result = new ArrayList<>();

int i = 0;
while (i < endpoints.size()) {
int[] epsi = endpoints.get(i);

if (height[epsi[0]] <= height[epsi[1]]) {
i++;
} else {
int[] curr = new int[] { epsi[0], epsi[1] };

int j = i + 1;
int mergedIndex = i;
while (j < endpoints.size()) {
int[] epsj = endpoints.get(j);

if (height[epsj[0]] >= height[epsi[0]]) {
mergedIndex = j - 1;
curr[1] = epsj[0];
break;
}

if (height[epsj[1]] >= height[curr[1]]) {
curr[1] = epsj[1];
mergedIndex = j;
if (height[curr[1]] > height[curr[0]]) {
break;
}
}

j++;
}