4 Methods to Solve Trapping Rain Water

A Quick Guide

Imagine a landscape with several blocks of different heights. When it rains, how much water can be trapped between the blocks?    The Trapping Rain Water problem aims to solve this....

Given an array of non-negative integers representing the elevation map, the task is to find the total volume of water that can be trapped after rain.

Problem Statement

It involves traversing the array to find the maximum height on the left and right of each element, and then computing the total water trapped using the minimum of the two heights.

Approach 1: Brute Force Approach

Time Complexity: O(N^2).  Space Complexity: O(1)

It stores the maximum heights to the left & right of each element in two separate arrays. These arrays help to calculate amount of water that can be trapped between blocks in a single traversal.

Approach 2- Dynamic Programming Approach

Time Complexity: O(N) + O(N) + O(N) = O(N), since the array is traversed thrice.  Space Complexity: O(N), since two arrays are needed.

Use a stack to track index of previous smaller blocks & keep track of the area between the current block A[i] and all the previous blocks with smaller heights, resulting in a single scan.

Approach 3: Using stacks

Time Complexity: O(N), since the array is traversed once.  Space Complexity: O(N). Stack takes O(N) space.

This approach reduces space complexity to O(1) by taking two pointers at left & right of the array, then calculates the water trapped in a given direction depending on height of the block.

Approach 4: Two Pointers Approach

From where you can download data science projects for free? 1. Kaggle  2. Google  3. Github

Learn how to successfully tackle the Trapping raining water problem.

Are you ready to level up your coding skills?

Step Up Your Game with InterviewBit Web Stories

Don't miss out on the chance to upskill yourself with IntervewBit's engaging web stories. 

“