# LeetCode: Trapping Rain Water DP C#

Please review for performance and C# style.

I already solved this question in 1 way. LeetCode: trapping rain water C#

I tried also the dynamic programming approch

https://leetcode.com/problems/trapping-rain-water/

using System;
using System.Linq;
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, TrapDynamicProgramming(height));
}

public int TrapDynamicProgramming(int[] height)
{
if (height == null || height.Length == 0)
{
return 0;
}

int ans = 0;
int size = height.Length;
var leftMax = Enumerable.Repeat(0, size).ToList();
var rightMax = Enumerable.Repeat(0, size).ToList();

//compute the max height from the left for each cell
//starting from the left
leftMax[0] = height[0];
for (int i = 1; i < size; i++)
{
leftMax[i] = Math.Max(height[i], leftMax[i - 1]);
}

//compute the max height from the right for each cell
//starting from the right..
rightMax[size - 1] = height[size - 1];
for (int i = size - 2; i >= 0; i--)
{
rightMax[i] = Math.Max(height[i], rightMax[i + 1]);
}

//the amount of water is the minimal between left and right height.
// and we need to remove the height of the cell, think of this
// like where the ground starts
for (int i = 1; i < size - 1; i++)
{
ans += Math.Min(leftMax[i], rightMax[i]) - height[i];
}

return ans;
}
}


There is no reason to use lists instead of arrays, new int[size] will give you an array full of 0s without any overhead.

You can get away with creating only one array (leftMax) and then while computing the values of rightMax, instead of saving them into an array, complete the full calculation of how much to add to ans. Like this:

public int TrapDynamicProgramming(int[] height)
{
if (height == null || height.Length == 0)
{
return 0;
}

int ans = 0;
int size = height.Length;
int[] leftMax = new int[size];

leftMax[0] = height[0];
for (int i = 1; i < size; i++)
{
leftMax[i] = Math.Max(height[i], leftMax[i - 1]);
}

int rightMax = height[size - 1];
for (int i = size - 2; i >= 0; i--)
{
rightMax = Math.Max(height[i], rightMax);
ans += Math.Min(leftMax[i], rightMax) - height[i];
}

return ans;
}