Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

Trapping Rain Water

Previous3SumNextMaximum sum of a subarray

Last updated 1 year ago

Array, Two Pointers

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length

  • 1 <= n <= 2 * 104

  • 0 <= height[i] <= 105

Assumptions:

  • There is no number calculation overflow.

  • There is no any negative value element.

Questions to Clarify:

  • What would be the size of the input array?

Solutions

The problem is about calculating the total amount of rainwater that can be trapped between bars of different heights. The solution involves iterating over each bar and calculating the amount of water that can be trapped on top of it.

For each bar, we find the maximum height of the bars to its left and right. The water that can be trapped on top of the current bar is the minimum of these two maximum heights minus the height of the current bar. This is because the water level cannot be higher than the shorter bar around it, and the height of the bar itself occupies space where water could have been trapped.

Approach – Brute Force Technique

This algorithm calculates the water trapped at each index by finding the maximum height of bars on the left and right side. The water trapped at a particular index is the minimum of these two maximum heights minus the height at that index.

Here, the area calculation formula for this problem is:

maxWater += min(maxLeft,maxRight) - height[current]

Steps

  1. Initialize totalWater to 0: This variable will keep track of the total amount of water that can be trapped.

  2. Iterate over each bar (from 0 to length of the array): For each bar, we calculate the amount of water that can be trapped on top of it.

  3. Find the maximum height of the bars on the left of the current bar: We initialize leftMax to 0 and iterate from the current bar to the first bar of the array, updating leftMax with the maximum height encountered.

  4. Find the maximum height of the bars on the right of the current bar: Similarly, we initialize rightMax to 0 and iterate from the current bar to the last bar of the array, updating rightMax with the maximum height encountered.

  5. Calculate the water trapped on the current bar: The amount of water that can be trapped on the current bar is the minimum of leftMax and rightMax minus the height of the current bar. This is because the water level cannot be higher than the shorter bar around it, and the height of the bar itself occupies space where water could have been trapped.

  6. Add the water trapped on the current bar to totalWater: We add the amount of water trapped on the current bar to totalWater.

  7. Return totalWater: After the loop finishes, totalWater will be the total amount of water that can be trapped according to the input array.

public class Solution
{
    public int Trap(int[] height)
    {

        int maxWater = 0;
        if (height != null && height.Length > 2)
        {
            for (int i = 0; i < height.Length; i++)
            {
                int leftP = i;
                int rightP = i;
                int maxLeft = 0;
                int maxRight = 0;

                while (leftP >= 0)
                {
                    maxLeft = Math.Max(maxLeft, height[leftP]);
                    leftP--;
                }

                while (rightP < height.Length)
                {
                    maxRight = Math.Max(maxRight, height[rightP]);
                    rightP++;
                }

                maxWater += Math.Min(maxLeft, maxRight) - height[i];
            }
        }

        return maxWater;
    }
}

Complexity

  • Time complexity: O(N^2)

  • Space complexity: O(1)

Approach – Two Pointers Technique

The problem is about calculating the total amount of rainwater that can be trapped between bars of different heights. The solution involves using two pointers, one starting from the beginning of the array (left) and the other from the end of the array (right).

The algorithm maintains two variables, maxLeft and maxRight, to keep track of the maximum height of the bars seen so far from the left and right, respectively.

In each step, the algorithm compares maxLeft and maxRight. If maxLeft is less than maxRight, it means the water trapped on the bar at the left index would be maxLeft - height[left], because maxLeft is the minimum of the two. So, it adds this to totalWater and moves the left pointer one step to the right.

If maxLeft is not less than maxRight, it does the same operation with the right pointer and maxRight.

The algorithm continues this process until the left and right pointers meet. At the end, totalWater will be the total amount of water that can be trapped according to the input array.

Steps

  1. Check if the array length is less than or equal to 2: If the array length is less than or equal to 2, there can't be any trapped water, so return 0.

  2. Initialize variables: n is the length of the array. maxLeft and maxRight are the maximum heights of the bars on the left and right ends of the array, respectively. left and right are pointers to the second bar from the left and the second bar from the right, respectively. totalWater is initialized to 0 to keep track of the total amount of trapped water.

  3. Start a while loop that continues as long as left is less than or equal to right: This loop traverses the array from both ends towards the center.

  4. Check if maxLeft is less than maxRight: If maxLeft is less than maxRight, then the water trapped on the current bar depends on maxLeft.

    • If the height of the bar at the left index is greater than maxLeft, update maxLeft to this height.

    • Otherwise, add maxLeft - height[left] to totalWater (this is the amount of water that the current bar can trap), and increment left by 1.

  5. If maxLeft is not less than maxRight, then the water trapped on the current bar depends on maxRight.

    • If the height of the bar at the right index is greater than maxRight, update maxRight to this height.

    • Otherwise, add maxRight - height[right] to totalWater (this is the amount of water that the current bar can trap), and decrement right by 1.

  6. Return totalWater: After the loop finishes, totalWater will be the total amount of water that can be trapped according to the input array.

public class Solution
{
    public int Trap(int[] height)
    {

        if (height?.Length <= 2) return 0;

        int n = height!.Length, maxLeft = height[0], maxRight = height[n - 1];
        int left = 1, right = n - 2, totalWater = 0;
        while (left <= right)
        {
            if (maxLeft < maxRight)
            {
                if (height[left] > maxLeft)
                    maxLeft = height[left];
                else
                    totalWater += maxLeft - height[left];
                left += 1;
            }
            else
            {
                if (height[right] > maxRight)
                    maxRight = height[right];
                else
                    totalWater += maxRight - height[right];
                right -= 1;
            }
        }
        return totalWater;
    }
}

Complexity

  • Time complexity: O(N)

  • Space complexity: O(1)