Trapping Rain Water | Leetcode 42 Solution

42. Trapping Rain Water

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

Solution :

Using Prefixmax array and suffixmax array : 

formula used :  

water stored at a particular index =  min(leftmaximum[i] , rightmaximum[i]) - a[i] ; 

class Solution { public:     int trap(vector<int>& nums) {                 vector<int>leftmaximum;           vector<int>rightmaximum(nums.size(), 0);           for(int i =0; i < nums.size() ; i++)           {               if(i ==0)               {                   leftmaximum.push_back(nums[i]);               }               else               {                   leftmaximum.push_back(leftmaximum.back() < nums[i] ? nums[i] : leftmaximum.back());               }           }           for(int i =nums.size() -1 ; i>=0 ; i--)           {               if(i == nums.size() -1)               {                   rightmaximum[nums.size() -1] = nums[nums.size() -1];               }               else               {                   rightmaximum[i] = (rightmaximum[i+1] < nums[i])?nums[i] : rightmaximum[i+1];               }           }           int sum =0;           for(int i =0; i< nums.size() ; i++)           {               sum += min(leftmaximum[i] , rightmaximum[i]) -nums[i];           }       return sum;     } };