Let's Code_: Leetcode Hard: Trapping Rain Water

Monday, July 18, 2022

Leetcode Hard: Trapping Rain Water

Problem Name: Trapping Rain Water

Problem Description: https://leetcode.com/problems/trapping-rain-water/

Problem Approach used: Calculate the amount of water this index would store with the knowledge of highest left and highest right tower. Then subtract the hight of the current tower as that's just conctrete, water can't seep into.

Time Complexity: O(n) worst-case time and space complexity.

Solution:

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        
        int maxHt = 0;
        for (int i=0; i<n; i++) {
            maxHt = Math.max (maxHt, height[i]);
            leftMax[i] = maxHt;
        }
        
        maxHt = 0;
        for (int i=n-1; i>=0; i--) {
            maxHt = Math.max (maxHt, height[i]);
            rightMax[i] = maxHt;
        }
        
        int totalWater = 0;
        int water = 0;
        for (int i=0; i<n; i++) {
            water = Math.min(leftMax[i], rightMax[i]) - height[i];
            totalWater += water;
        }
        
        return totalWater;
    }
}