The given solution seems a little verbose, I believe it can be done in a single loop while keeping track of both the total water trapped and possible amount trapped at each point; this would also handle multiple water catchments in the same series of elevations:
def trapping_rain_water(elevations: List[int]) → int:
possible_trapped = 0
total_trapped = 0
curr_highest = -float(‘inf’)
for e in elevations:
if e >= curr_highest:
curr_highest = e
total_trapped += possible_trapped
else:
possible_trapped += curr_highest - e
return total_trapped
It can be done in O(1) space complexity by moving from left and right in opposite way, and keep track of maximum left and right, then calculate the trapped water by decrementing current elevation from max left or right
function trappingRainWater(elevations) {
let l = 0, r = elevations.length - 1;
let maxl = 0, maxr = 0;
let trappedWater = 0;
while(l < r) {
if (elevations[l] < elevations[r]) {
maxl = Math.max(maxl, elevations[l]);
trappedWater += maxl - elevations[l];
l++
} else {
maxr = Math.max(maxr, elevations[r]);
trappedWater += maxr - elevations[r];
r--;
}
}
return trappedWater;
}
This does not work. Example input: [4,2,3].
We need to consider both left and right walls to know possible_trapped.
The solution is DP, Two Pointes should be much simpler:
int trapping_rain_water(std::vector elevations) {
int pl = 0, pr = elevations.size() - 1;
int left = elevations[pl], right = elevations[pr];
int trapped = 0;
while (pl <= pr) {
if (left <= right) {
int height = elevations[pl++];
left = std::max(left, height);
trapped += left - height;
} else {
int height =elevations[pr–];
right = std::max(right, height);
trapped += right - height;
}
}
return trapped;
}
why does the answer gives [2, 1, 3] 0? in the image, it shows 1
The answer of [2,1,3] should be 1.
from typing import List
def trapping_rain_water(elevations: List[int]) → int:
# WRITE YOUR BRILLIANT CODE HERE
left, right = 0, len(elevations) - 1
trapped = 0
boundary = 0
while left < right:
left_elevation = elevations[left]
right_elevation = elevations[right]
cur_boundary = max(left_elevation, right_elevation)
boundary = max(cur_boundary, boundary)
if left_elevation <= boundary:
trapped += boundary - left_elevation
left += 1
if right_elevation <= boundary:
trapped += boundary - right_elevation
right -= 1
return trapped
This solution fails for “3 2 1 2 2 3 1”
Here is my try at the java solution:
public static int trappingRainWater(List elevations) {
int[] leftToRight = new int[elevations.size()];
int[] rightToLeft = new int[elevations.size()];
int trapped = 0;
leftToRight[0] = elevations.get(0);
for(int i = 1; i < elevations.size(); i++) {
leftToRight[i] = Math.max(leftToRight[i-1], elevations.get(i));
}
rightToLeft[elevations.size() - 1] = elevations.get(elevations.size() - 1);
for(int i = elevations.size() - 2; i>=0; i–)
rightToLeft[i] = Math.max(rightToLeft[i+1], elevations.get(i));
for(int i = 0; i < elevations.size(); i++)
trapped += Math.min(leftToRight[i], rightToLeft[i]) - elevations.get(i);
return trapped;
}
c# single loop
public static int TrappingRainWater(List elevations)
{
if (elevations == null || elevations.Count < 3)
{
return 0;
}
var sum = 0;
var walls = new int[elevations.Count];
var left = 1;
var right = elevations.Count - 2;
while (left < elevations.Count - 1)
{
if (left < right)
{
walls[left] = Math.Max(elevations[left - 1], walls[left - 1]);
walls[right] = Math.Max(elevations[right + 1], walls[right + 1]);
}
else if (left > right)
{
var height1 = Math.Min(walls[left], walls[left - 1]);
walls[left] = height1;
if (height1 > elevations[left])
{
sum += height1 - elevations[left];
}
var height2 = Math.Min(walls[right], walls[right + 1]);
walls[right] = height2;
if (height2 > elevations[right])
{
sum += height2 - elevations[right];
}
}
else
{
var leftWall = Math.Max(elevations[left - 1], walls[left - 1]);
var rightWall = Math.Max(elevations[right + 1], walls[right + 1]);
var height = Math.Min(leftWall, rightWall);
walls[left] = height;
if (height > elevations[left])
{
sum += height - elevations[left];
}
}
left++;
right--;
}
return sum;
}
Perfect solution, thanks!
It works in O(1) space complexity and O(n) time complexity with lower constant (1 loop instead of 3 as for AM solution)
The tests are clearly not thorough enough. Incorrect code can pass these two test cases.
Using indeed two pointers:
public static int trappingRainWater(List elevations) {
int left = 0, right = 0;
int totalTrapped = 0;
int countTrapped = 0;
while (right < elevations.size()) {
if (elevations.get(right) >= elevations.get(left) && right > left) {
totalTrapped += countTrapped;
countTrapped = 0;
left = right;
continue;
}
int diff = elevations.get(left) - elevations.get(right);
countTrapped += diff;
right++;
}
return totalTrapped;
}
This can be done in O(1) space as well.
This solution is O(n) space. This is a O(1) space solution.
def trapping_rain_water(e: List[int]) → int:
# WRITE YOUR BRILLIANT CODE HERE
l, r = 0, len(e)-1
total = 0
ml, mr = 0,0
while l < r:
if e[l] < e[r]:
total += max(0, ml-e[l])
ml = max(ml, e[l])
l +=1
else:
total += max(0, mr-e[r])
mr = max(mr, e[r])
r -=1
return total