Table of contents
Problem - Leetcode
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 rain.
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<sup>4</sup>
0 <= height[i] <= 10<sup>5</sup>
Answer-1 in Golang
func trap(height []int) int {
if height == nil {
return 0
}
left, right := 0, len(height)-1
leftMax, rightMax := height[left], height[right]
result := 0
for left < right {
if leftMax < rightMax {
left++
leftMax = max(leftMax, height[left])
result = result + leftMax - height[left]
} else {
right--
rightMax = max(rightMax, height[right])
result = result + rightMax - height[right]
}
}
return result
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
This code defines a function trap
in Go that calculates the amount of trapped rainwater between bars of varying heights represented by the height
array. It uses a two-pointer approach to find the trapped water. Here's a detailed breakdown of the code:
The
trap
function takes an input arrayheight
which represents the heights of bars.It checks if the input array is nil, and if so, returns 0 (since there's no trapped water if there are no bars).
Initialize two pointers
left
andright
to the beginning and end of theheight
array, respectively.Initialize two variables
leftMax
andrightMax
to store the maximum height encountered on the left and right sides, both initialized to the heights of the first and last bars.Initialize a variable
result
to store the total trapped rainwater, initially set to 0.Enter a
for
loop while theleft
pointer is less than theright
pointer:Compare
leftMax
andrightMax
to determine which side has a smaller maximum height.If
leftMax
is smaller, increment theleft
pointer, updateleftMax
to the new maximum height, and add the difference betweenleftMax
and the height atheight[left]
toresult
.If
rightMax
is smaller (or equal), decrement theright
pointer, updaterightMax
to the new maximum height, and add the difference betweenrightMax
and the height atheight[right]
toresult
.
Once the
for
loop ends (whenleft
is no longer less thanright
), return theresult
variable, which contains the total trapped rainwater.The
max
function is a utility function that takes two integersa
andb
and returns the maximum of the two.
The overall idea behind this code is to calculate the trapped rainwater by comparing the heights of the bars on the left and right sides. It iterates through the bars using the two-pointer approach and keeps track of the maximum heights encountered. By calculating the difference between the maximum height and the current height at each step, it accurately calculates the trapped rainwater.