# LeetCode: trapping rain water C#

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.

Example:

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


Please review for performance.

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
/// <summary>
/// https://leetcode.com/problems/trapping-rain-water/
/// </summary>
[TestClass]
public class TrappingRainWater
{
[TestMethod]
public void TestMethod1()
{
int[] height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
Assert.AreEqual(6, Trap(height));
}

public int Trap(int[] height)
{
int left = 0;
int right = height.Length - 1;
int ans = 0;
int leftMax = 0;
int rightMax = 0;
while (left < right)
{
if (height[left] < height[right])
{
//if height left < left max that means we can trap water
if (height[left] < leftMax)
{
ans += leftMax - height[left];
}
else // otherwise left max needs to be updated
{
leftMax = height[left];
}
left++;
}
else
{
if (height[right] < rightMax)
{
ans += rightMax - height[right];
}
else
{
rightMax = height[right];
}

right--;
}
}
return ans;
}
}
}

• Seems perfect to me, O(1), only 2 quick if statements per iteration, minimal math. – potato Jun 11 at 13:15
• correction: O(n) – potato Jun 11 at 13:24