Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
trap rain water - use linear scan algorithm - two iterations
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
keywords:
integer array, arr[i] >= 0 for any i, representing width of each bar = 1, height[i] = arr[i]
ask: how much water it is able to trap after raining
---
--- ---
--- --- ---
brute force solution ->left = 1, right = 2, itself = 0, naive store min(left, right) - arr[i] -> O(n)
time complexity: O(n^2) - brute force - efficient
[2, 1, 0, 1, 3]
-> 3
[0, 1, 2, 1, 0]
->
[4, 1, 0, 1, 3]
->
[0, 3, 4, 3, 1]
-> left to right
-> right to left
-> get minimum for two iteration, find the sum O(n)
descending stack: [2, 1, 0,] -> maximum height = 2
ascending stack: [0, 1, 3] -> maximum height = 3
-> left to right linear time complexity ->
[3, 4, 5] -> descending order
[5, 6, 7]
range from index = 3 to 7, height -> water height = min(2, 3) = 2
public int trap(int[] height) {
if(height == null)
return 0;
var length = height.Length();
// two iterations - left to right
//[2, 1, 0, 1, 3]
//-> 3
//[0, 1, 2, 1, 0]
var leftToRight = ScanFromLeftToRight(height);
var rightToLeft = ScanFromLeftToRight(Array.Reverse(height)); // <- [1, 2, 3] -> [3, 2, 1] -> left to right
rightToLeft = Array.Reverse(rightToLeft);
// get the minimum of both
for()
// get the sum of two array
}
private static int[] ScanFromLeftToRight(int[] height)
{
var leftToRight = new int[length];
var max = height[0];
for(int index = 0; index < length; index++)
{
var current = leftToRight[index];
if(current > max)
{
max = current;
leftToRight[index] = 0;
}
else
{
leftToRight[index] = max - current;
}
}
return leftToRight;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.