Trapping Rain Water - The Prefix & Suffix Max Approach (Java)

"Trapping Rain Water" (LeetCode #42). This problem is a staple in coding interviews and is excellent for sharpening array manipulation and thought process skills.

While it's rated "Hard," we'll break it down using an intuitive approach involving prefix and suffix maximums, making the logic clear and understandable. Let's dive into how we can calculate the maximum water trapped between elevation bars!

We are given an array height of non-negative integers. Each height[i] represents the height of a bar, which has a width of 1. Our goal is to return the total amount of water that can be trapped between these bars after it rains.

Imagine this as an elevation map. Water can only be trapped in "dips" or "valleys" between taller bars. The amount of water a specific bar at index i can hold depends on the height of the tallest bar to its left and the tallest bar to its right.

Example:

• Input: height = [0, 2, 0, 3, 1, 0, 1, 3, 2, 1]

• Output: 9

Let's visualize the example:

  #
# # #   #
# # # # # # #
_ _ _ _ _ _ _ _ _ _
0 2 0 3 1 0 1 3 2 1  (Heights)

The trapped water would fill the gaps, for instance:

• Between height 2 and 3: 2 units (0 -> 2)

• Between height 3 and 3: 1 unit (1 -> 1), 2 units (0 -> 2), 1 unit (1 -> 1)

• ... and so on.

  My Thought Process & Approach (Prefix and Suffix Maximums):

The key insight for this problem is realizing that the amount of water trapped above a particular bar at index i is determined by the minimum of the maximum height to its left and the maximum height to its right, minus the bar's own height.

• water_above_bar[i] = min(max_left_height[i], max_right_height[i]) - height[i]

If min(max_left_height[i], max_right_height[i]) - height[i] is negative or zero, it means no water can be trapped above that bar (it's either a peak or as tall as its surroundings). We only add positive amounts.

To efficiently find max_left_height[i] and max_right_height[i] for every position i, we can use two auxiliary arrays:

1. pfmax (Prefix Maximums): This array will store, for each index i, the maximum height encountered from the beginning of the array up to i.

   • pfmax[0] = height[0]

   • pfmax[i] = Math.max(height[i], pfmax[i-1]) for i > 0

2. sfmax (Suffix Maximums): This array will store, for each index i, the maximum height encountered from the end of the array down to i.

   • sfmax[n-1] = height[n-1]

   • sfmax[i] = Math.max(height[i], sfmax[i+1]) for i < n-1

Once we have these two arrays, a final pass through the height array allows us to calculate the trapped water:

1. Iterate and Calculate Water:

   • Initialize totalWaterTrapped = 0.

   • Loop from i = 0 to n-1.

   • For each index i, calculate the potential water above height[i]: currentBarWater = Math.min(pfmax[i], sfmax[i]) - height[i]

   • If currentBarWater is greater than 0, add it to totalWaterTrapped.

   • Return totalWaterTrapped.

This approach clearly breaks down the problem into manageable steps, using pre-calculated maximums to avoid repeated computations.

Java Code Implementation:

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] pfmax = new int[n];
        int[] sfmax = new int[n];
        pfmax[0] = height[0];
        sfmax[n-1] = height[n-1]; 
        for(int i =1;i<n;i++){
            pfmax[i] = Math.max(height[i],pfmax[i-1]);
        }
        for(int i = n-2; i>=0; i--){
            sfmax[i] = Math.max(height[i],sfmax[i+1]);
        }
        int water = 0;
        for(int i=0;i<n;i++){
           int ans=  Math.min(pfmax[i],sfmax[i]) - height[i];
           if(ans>0){
            water+=ans;
           }
        }
        return water;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(N)

  • The first loop for pfmax runs N times.

  • The second loop for sfmax runs N times.

  • The third loop for calculating totalWaterTrapped runs N times.

  • Each operation inside these loops (array access, Math.max, Math.min, addition) is constant time.

  • Therefore, the total time complexity is O(N) + O(N) + O(N) = O(N). This is optimal as we must at least look at every bar.

• Space Complexity: O(N)

  • We use two auxiliary arrays, pfmax and sfmax, each of size N.

  • Therefore, the total space complexity is O(N) + O(N) = O(N).