I tried nLog(n) and passed. but this is a O(n) solution.

```
/**
* Solution II: Passed, O(n)
* From left to right, fill water to the max height so far.
* From right to left, fill water to the max height so far.
* Iterate through, for each position, pick the min of 2 heights.
* Calculate volume.
*
* We can view this as sort of "greedy":
* 1. always fill water to the max from 1 side.
* 2. but have to verify if we will find an equal or higher edge on the other side.
* 3. thus we go directions and pick the smaller height at each index.
*/
public int trap(int[] A) {
// edge case
if (A == null || A.length <= 1)
return 0;
int max = 0;
int[] heights1 = new int[A.length];
for (int i = 0; i < A.length; i++) {
int curr = A[i];
if (curr > max)
max = curr;
heights1[i] = max;
}
max = 0;
int[] heights2 = new int[A.length];
for (int i = A.length - 1; i >= 0; i--) {
int curr = A[i];
if (curr > max)
max = curr;
heights2[i] = max;
}
int volume = 0;
for (int i = 0; i < A.length; i++)
volume += Math.min(heights1[i], heights2[i]) - A[i];
return volume;
}
```