2
\$\begingroup\$

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/

enter image description here

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;
        }
}
\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.