Why is the DP solution not working, 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: 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.

**Constraints**:

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

The issue with this is that it is outputting 0 for when the input is [2,0,2] but the code should be setting the index 1 to have a leftMax of 2 and rightMax of 2 so 2-0=2 should be the output

class Solution {
    public int trap(int[] height) {
        
        if(height == null || height.length == 0){
            return 0;
        }
        
        int ans = 0;
        int size = height.length;
        
        int[] leftMax = new int[size];
        int[] rightMax = new int[size];
        
        leftMax[0] = height[0];
        for(int i = 1; i < size; i++){
            leftMax[i] = Math.max(leftMax[i-1],height[i]);
        }
        
        rightMax[0] = height[size-1];
        for(int i = size-2; i >= 0; i--){
            rightMax[i] = Math.max(rightMax[i+1],height[i]);
        }
        
        for(int i = 1; i < size-1; i++){
            ans+= Math.min(leftMax[i],rightMax[i])-height[i];
        }
        return ans;
    }
}

Answer

The problem is that your rightMax initialization is wrong, it initializes “on the wrong side”. It initializes the [0] which was probably copied from the leftMax section. But the leftMax then iterates from the left, the rightMax iterates from the right and therefore the rightmost index should be initialized. Note that you already initialized with the correct height index but for the wrong rightMax – it should look like:

rightMax[size-1] = height[size-1]

This previously worked because the very right was (probably) not part of a water trap and therefore its wrong value did not have any impact. But in the very simply case of 2,0,2 it is part of the trap and messed up the result.

Now the code properly calculates the two given samples:

System.out.println(trap(new int[] {0,1,0,2,1,0,1,3,2,1,2,1})); // 6
System.out.println(trap(new int[] {2,0,2})); // 2

Leave a Reply

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