151 DSA Problem journey

GAURAV YADAVGAURAV YADAV
2 min read

Q14: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 :

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.

Solution:
class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size()-1, level = 0, water = 0;
    while (l < r) {
        int lower = height[height[l] < height[r] ? l++ : r--];
        level = max(level, lower);
        water += level - lower;
    }
    return water;      
    }
};

Explantion:
>The code uses a two-pointer approach (l and r) to traverse the height vector from both ends.
>level represents the current height of the water, and water is the accumulated water.
>The loop continues until the left pointer l is less than the right pointer r.
>The smaller of the two heights at the current pointers (l and r) is determined 
and stored in the variable lower.
>level is updated to be the maximum of its current value and the lower height.
>The amount of water trapped between the current height and the lower height is 
calculated and added to the water variable.
>The process continues until the entire vector is processed.
>The total accumulated water is returned as the result.

If anyone have better solution so please comment:)
18
Subscribe to my newsletter

Read articles from GAURAV YADAV directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

GAURAV YADAV
GAURAV YADAV

Experienced Full Stack Developer with proficiency in comprehensive coding skills, adept at crafting end-to-end solutions.