Problem Statement

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 * 10⁴
0 <= height[i] <= 10⁵

Trapping Rain Water Logic

O(n) Solution With Extra space

For each index we will need what is the max height on left as well as on right.
So we will need to arrays to maintain this information for each index.
PrefixMax
- We will calculate prefixMax array by traversing from left to right and keep updating max height as per the running max height.
Similarly we will prepare suffixMax array.
In the end, we will use this info and height[i] to calculate how many water unit can be trapped.
- Formula : min(suffixMax[i], prefixMax[i]) – height[i]

Golang solution for Trapping Rain Water

func trap(height []int) int {
	length := len(height)
	left := 0
	right := length - 1
	prefixMax := make([]int, length)
	suffixMax := make([]int, length)

	if length < 3 {
		return 0
	}

	prefixMax[left] = height[left]
	suffixMax[right] = height[right]

	totalTrappedWater := 0

	// iterate over the height array and prepare prefixMax
	for left = 1; left < length; left++ {
		if prefixMax[left-1] < height[left] {
			prefixMax[left] = height[left]
		} else {
			prefixMax[left] = prefixMax[left-1]
		}
	}
	// iterate over the height array and prepare suffixMax
	for right = length - 2; right > 0; right-- {
		if suffixMax[right+1] < height[right] {
			suffixMax[right] = height[right]
		} else {
			suffixMax[right] = suffixMax[right+1]
		}
	}

	// calculate totalTrappedWater
	for i := 1; i < length-1; i++ {
		if height[i] < prefixMax[i] && height[i] < suffixMax[i] {
			diff := prefixMax[i]
			if prefixMax[i] > suffixMax[i] {
				diff = suffixMax[i]
			}
			waterUnit := diff - height[i]

			if waterUnit > 0 {
				totalTrappedWater += waterUnit
			}
		}

	}

	return totalTrappedWater
}

Updated Version

func trap(height []int) int {
	length := len(height)
	if length < 3 {
		return 0
	}

	// Initialize prefixMax and suffixMax arrays
	prefixMax := make([]int, length)
	suffixMax := make([]int, length)

	// Set initial values for prefixMax and suffixMax
	prefixMax[0] = height[0]
	suffixMax[length-1] = height[length-1]

	// Build prefixMax array
	for i := 1; i < length; i++ {
		prefixMax[i] = max(prefixMax[i-1], height[i])
	}

	// Build suffixMax array
	for i := length - 2; i >= 0; i-- {
		suffixMax[i] = max(suffixMax[i+1], height[i])
	}

	// Calculate total trapped water
	totalTrappedWater := 0
	for i := 1; i < length-1; i++ {
		waterUnit := min(prefixMax[i], suffixMax[i]) - height[i]
		if waterUnit > 0 {
			totalTrappedWater += waterUnit
		}
	}

	return totalTrappedWater
}

// Helper functions to get max and min
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

O(n) solution WITHOUT Extra space

Optimised Solution

Version-1

func trap(height []int) int {

	n := len(height)
	leftPtr := 0
	rightPtr := n - 1
	leftMax := height[leftPtr]
	rightMax := height[rightPtr]
	waterTrapped := 0

	for leftPtr <= rightPtr {
		if leftMax <= rightMax {
			leftMax = max(leftMax, height[leftPtr])
			waterUnit := min(leftMax, rightMax) - height[leftPtr]
			if waterUnit > 0 {
				waterTrapped = waterTrapped + waterUnit
			}
			leftPtr++
		} else {
			rightMax = max(rightMax, height[rightPtr])
			waterUnit := min(leftMax, rightMax) - height[rightPtr]
			if waterUnit > 0 {
				waterTrapped = waterTrapped + waterUnit
			}
			rightPtr--
		}
	}
	return waterTrapped
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Version-2

This is kind of similar to Kadane’s algorithm workflow i.e. it uses similar intuition thought process.

package main

import (
	"fmt"
)

// trap calculates the total amount of water trapped after raining
func trap(height []int) int {
	n := len(height)

	// Initialize two pointers: leftPtr starting from the left end and rightPtr from the right end
	leftPtr := 0
	rightPtr := n - 1

	// Track the maximum heights encountered from the left and right sides
	leftMax := height[leftPtr]
	rightMax := height[rightPtr]

	// Variable to accumulate total trapped water
	waterTrapped := 0

	// Traverse the array using two pointers
	for leftPtr <= rightPtr {
		// Process the smaller height side first
		// If the leftMax is less than or equal to the rightMax, we can safely calculate water trapped at leftPtr
		if leftMax <= rightMax {
			// Update leftMax if current height is greater
			leftMax = max(leftMax, height[leftPtr])

			// Calculate water trapped at the current leftPtr (difference between leftMax and current height)
			waterTrapped += leftMax - height[leftPtr]

			// Move the left pointer to the right
			leftPtr++
		} else {
			// If rightMax is less than leftMax, calculate water trapped at rightPtr
			rightMax = max(rightMax, height[rightPtr])

			// Calculate water trapped at the current rightPtr (difference between rightMax and current height)
			waterTrapped += rightMax - height[rightPtr]

			// Move the right pointer to the left
			rightPtr--
		}
	}

	// Return the total amount of trapped water
	return waterTrapped
}

// Helper function to find the maximum of two integers
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	// Example height array
	height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}

	// Output the result of the trap function
	fmt.Println("Total water trapped:", trap(height)) // Expected output: 6
}

Key Explanations

Initialization:
- leftPtr and rightPtr are used to traverse the height array from both ends.
- leftMax and rightMax track the maximum heights encountered from the left and right sides respectively.
Two-pointer Logic:
- The algorithm processes the side (left or right) with the smaller maximum height first. This ensures that any trapped water can be calculated correctly because the side with the smaller height will limit the water that can be trapped.
- The trapped water at any position is calculated as the difference between the maximum height up to that point (leftMax or rightMax) and the current height.
Efficiency:
- Time Complexity: O(n) because each element is processed once.
- Space Complexity: O(1), using only a few variables, with no additional space proportional to the input size.

This is an optimal and correct solution for the trapping rainwater problem.

Visit https: https://codeandalgo.com for more such contents

CODE & ALGO

Trapping Rain Water

Table of Contents