1
\$\begingroup\$

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. enter image description here

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;
        }
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Seems perfect to me, O(1), only 2 quick if statements per iteration, minimal math. \$\endgroup\$ – potato Jun 11 at 13:15
  • 2
    \$\begingroup\$ correction: O(n) \$\endgroup\$ – potato Jun 11 at 13:24

Your Answer

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

Browse other questions tagged or ask your own question.