Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1].
In this case, 6 units of rain water (blue section) are being trapped.
Solution I: (Brute Force)
Approach:
Finding the left max and right max from a point.
Finding water level by subtracting height from min(left max , right max)
class Solution
{
public:
int trap(vector<int> &height)
{
int s = 0;
for (int i = 0; i < height.size(); i++)
{
int lMax = 0;
int rMax = 0;
for (int j = i; j >= 0; j--)
{
if (height[j] > lMax)
{
lMax = height[j];
}
}
for (int j = i; j < height.size(); j++)
{
if (height[j] > rMax)
{
rMax = height[j];
}
}
int x = min(lMax, rMax) - height[i];
if (x > 0)
{
s = s + x;
}
}
return s;
}
};
Time Complexity: O(N^2)
Solution II: (DP)
class Solution
{
public:
int trap(vector<int> &height)
{
int n = height.size();
if (n == 0)
{
return 0;
}
vector<int> lm(n, 0);
vector<int> rm(n, 0);
lm[0] = 0;
int lh = height[0];
for (int i = 1; i < n; i++)
{
lm[i] = lh;
lh = max(lh, height[i]);
}
rm[n - 1] = 0;
int rh = height[n - 1];
for (int i = n - 2; i >= 0; i--)
{
rm[i] = rh;
rh = max(rh, height[i]);
}
int water = 0;
for (int i = 0; i < n; i++)
{
int amount = min(lm[i], rm[i]) - height[i];
water += (amount > 0) ? amount : 0;
}
return water;
}
};
Time Complexity: O(N)
Solution III: (Two Pointer)
class Solution
{
public:
int trap(vector<int> &height)
{
int s = 0;
int lMax = 0;
int rMax = 0;
int l = 0;
int r = height.size() - 1;
while (l < r)
{
if (height[l] < height[r])
{
if (height[l] >= lMax)
{
lMax = height[l];
}
else
{
s = s + lMax - height[l];
}
l++;
}
else
{
if (height[r] >= rMax)
{
rMax = height[r];
}
else
{
s = s + rMax - height[r];
}
r--;
}
}
return s;
}
};