[Solved] 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.

Question

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:

rainwatertrap
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

Python Solution

class Solution:
    def trap(self, A: List[int]) -> int:
        water = 0
        left = 0
        right = len(A)-1

        left_biggest_wall = 0
        right_biggest_wall = 0

        while left < right:
            if A[left] < A[right]:
                left_biggest_wall = max(left_biggest_wall,A[left])
                if A[left] < left_biggest_wall:
                    water += left_biggest_wall-A[left]
                left +=1

            else:
                right_biggest_wall = max(right_biggest_wall,A[right])
                if A[right] < right_biggest_wall:
                    water += right_biggest_wall-A[right]
                right-=1

        return(water)
Abhishek Sharma
Abhishek Sharma

Started my Data Science journey in my 2nd year of college and since then continuously into it because of the magical powers of ML and continuously doing projects in almost every domain of AI like ML, DL, CV, NLP.

Articles: 520

Subscribe to our Newsletter

Subscribe to our newsletter and receive all latest projects...

Leave a Reply

Your email address will not be published. Required fields are marked *