The Rain Water Trapping problem is a classic problem in computer science that involves calculating the amount of water that can be trapped between bars of different heights in a bar chart. In this problem, the bar chart is represented as an array of non-negative integers, where each element represents the height of a bar. The bars can be of different heights and the width of each bar is assumed to be 1 unit.
When it rains, the water is trapped between the bars and the goal is to calculate the total amount of water that can be trapped. The bars on the edges of the bar chart cannot trap water, as there is no bar to their left or right, respectively.
Example : N = 6, arr[] = {3,0,0,2,0,4}
4 |
3 | |
2 | | |
1 | | |
3 0 0 2 0 4
We have to calculate total water trapped between this block.
from block 1 = 0
from block 2 = 3
from block 3 = 3
from block 4 = 1
from block 5 = 3
from block 6 = 0
total water trapped = 10
Here’s an implementation of the Rain Water Trapping problem in Kotlin:
fun trap(height: IntArray): Int {
var left = 0
var right = height.size - 1
var leftMax = 0
var rightMax = 0
var result = 0
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left]
} else {
result += leftMax - height[left]
}
left++
} else {
if (height[right] >= rightMax) {
rightMax = height[right]
} else {
result += rightMax - height[right]
}
right--
}
}
return result
}This function takes an integer array height as input, where each element represents the height of a bar in a bar chart. The goal is to calculate the total amount of water that can be trapped between the bars. The algorithm works by using two pointers, one pointing to the leftmost bar and one pointing to the rightmost bar. It also keeps track of the maximum height of bars to the left and right of the current position.
At each step, it compares the heights of the bars at the left and right pointers, and moves the pointer pointing to the smaller bar. If the height of the current bar is less than the maximum height to its left (or right), it means that some water can be trapped at that position, so we add the difference between the maximum height and the current height to the result. Finally, we return the result, which represents the total amount of water that can be trapped between the bars.
fun trap(height: IntArray): Int {
var left = 0
var right = height.size - 1
var leftMax = 0
var rightMax = 0
var result = 0
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left]
} else {
result += leftMax - height[left]
}
left++
} else {
if (height[right] >= rightMax) {
rightMax = height[right]
} else {
result += rightMax - height[right]
}
right--
}
}
return result
}
fun main() {
val heights = intArrayOf(3,0,0,2,0,4)
val waterTrapped = trap(heights)
println(waterTrapped) // Output: 10
}In this example, the input array heights represents the bar chart [3, 0, 0, 2, 0, 4], and the output is 10, which represents the total amount of water that can be trapped between the bars.