Trapping Rainwater in c#

Programming C#
1

The “Trapping Rainwater” problem involves calculating how much rainwater can be trapped between bars of varying heights. The goal is to find the amount of water that can be stored after raining, given the heights of the bars.

Approach

To solve this problem, we can use a two-pointer technique, which is efficient and easy to implement. Here’s how the algorithm works:

  1. Initialize Two Pointers: Start with two pointers, one at the left end (left) and one at the right end (right) of the array.

  2. Track Maximum Heights: Maintain two variables to track the maximum heights encountered from both the left and right sides (leftMax and rightMax).

  3. Move the Pointers:

    • Compare the heights at the two pointers.
    • If the height at the left pointer is less than or equal to the height at the right pointer, check if leftMax is greater than the height at the left pointer. If it is, water can be trapped, and we add the difference to the total water trapped. Update leftMax if the height at the left pointer is greater.
    • If the height at the right pointer is less than the height at the left pointer, do the same for the right pointer.

  4. Continue Until Pointers Meet: Repeat the process until the left pointer meets the right pointer.

Implementation in C#

Here’s a C# implementation of the above approach:

using System;

public class Program
{
    public static void Main()
    {
        int[] heights = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 }; // Example heights
        int trappedWater = TrapRainwater(heights);
        Console.WriteLine($"Total trapped rainwater: {trappedWater}");
    }

    public static int TrapRainwater(int[] heights)
    {
        if (heights == null || heights.Length == 0) return 0;

        int left = 0, right = heights.Length - 1;
        int leftMax = 0, rightMax = 0;
        int totalWater = 0;

        while (left < right)
        {
            if (heights[left] <= heights[right])
            {
                if (heights[left] >= leftMax)
                {
                    leftMax = heights[left];
                }
                else
                {
                    totalWater += leftMax - heights[left];
                }
                left++;
            }
            else
            {
                if (heights[right] >= rightMax)
                {
                    rightMax = heights[right];
                }
                else
                {
                    totalWater += rightMax - heights[right];
                }
                right--;
            }
        }

        return totalWater;
    }
}

Explanation:

  1. Input Array: The heights array represents the heights of the bars.

  2. Initial Conditions:

    • Check if the input is valid (non-null and not empty).
    • Initialize pointers (left and right), maximum height trackers (leftMax and rightMax), and a counter for total trapped water (totalWater).

  3. Two-Pointer Logic:

    • Use a while loop to process the heights until the left pointer is less than the right pointer.
    • Depending on the comparison of the heights at the two pointers, update the respective maximum height and calculate trapped water if the current height is less than the maximum.

  4. Return Result: After the loop, return the total amount of trapped water.

Complexity:

  • Time Complexity: ( O(n) ), where ( n ) is the length of the input array, since we traverse the array once.
  • Space Complexity: ( O(1) ), as we only use a constant amount of additional space for the pointers and variables.

This approach is efficient and straightforward, making it a popular choice for solving the trapping rainwater problem.