Skip to content

Instantly share code, notes, and snippets.

@hsaputra
Created November 9, 2018 22:39
Show Gist options
  • Save hsaputra/ec320d493bcc18ea67d2d4efd8dbdd6b to your computer and use it in GitHub Desktop.
Save hsaputra/ec320d493bcc18ea67d2d4efd8dbdd6b to your computer and use it in GitHub Desktop.
class Solution {
public int trap(int[] height) {
int count = 0;
int left = 0;
int right = height.length - 1;
int maxLeft = 0;
int maxRight = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] > maxLeft) {
maxLeft = height[left];
} else {
// We have trap
count += maxLeft - height[left];
}
left++;
} else {
if (height[right] > maxRight) {
maxRight = height[right];
} else {
// we have a trap
count += maxRight - height[right];
}
right--;
}
}
return count;
}
}
@hsaputra
Copy link
Author

hsaputra commented Nov 9, 2018

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.


The above elevation map 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. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment