LeetCode: Trapping Rain Water DP C#

Question

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;
        }
}

potato · Accepted Answer · 2020-03-17 07:42:55Z

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;
}

Stack Exchange Network

LeetCode: Trapping Rain Water DP C#

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

LeetCode: Trapping Rain Water DP C#

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions