# A O(n) solution

• 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;
}``````

• All right, this O(n) solution is simpler, it only requires 1 iteration.

``````/**
* O(n)
* use 2 pointers from left and right, moving toward either other.
* assume left < right;
*  keep moving left and fill the gaps,
*  height of water = max height so far,
*  stop when encounter a left > right.
* do the same for right, until encounter a right > left.
* switch between left and right, hold the larger one and move the
* smaller one.
*/
public int trap(int[] A) {
// edge case
if (A == null || A.length <= 1)
return 0;

int[] heights = new int[A.length];
int left = 0, right = A.length - 1;
int leftMax = 0, rightMax = 0;
while (left <= right) {
int leftHeight = A[left];
int rightHeight = A[right];
if (leftHeight <= rightHeight) {
if (leftHeight > leftMax)
leftMax = leftHeight;
// right is higher, so the height is purely
// determined by the max height on left.
heights[left] = leftMax;
left++;
} else {
if (rightHeight > rightMax)
rightMax = rightHeight;
heights[right] = rightMax;
right--;
}
}

int volume = 0;
for (int i = 0; i < A.length; i++)
volume += heights[i] - A[i];

return volume;
}``````

• Here is what I thought of... it does not required creating a new array and time complexity is O(n)

int trap(int A[], int n) {
if( n==0 || n==1 ){
return 0;
}

``````	int maxID =0, max=0;
for( int i=0; i<n ; i++ ){
if (max < A[i]) {
max = A[i];
maxID = i;
}
}

int totalWater = 0;
int currentLevel = A[0];
int currentStorage = 0;

for (int i=0 ; i<maxID; i++ ){
if ( currentLevel >= A[i] ){
currentStorage = currentStorage + currentLevel - A[i];
}
else {
totalWater = totalWater + currentStorage;
currentStorage = 0;
currentLevel = A[i];
}
}
totalWater = totalWater + currentStorage;

currentLevel = A[n-1];
currentStorage = 0;

for (int i=n-1 ; i>maxID; i-- ){
if ( currentLevel >= A[i] ){
currentStorage = currentStorage + currentLevel - A[i];
}
else {
totalWater = totalWater + currentStorage;
currentStorage = 0;
currentLevel = A[i];
}
}
totalWater = totalWater + currentStorage;