Kotlin coding test course, calculating the amount of water

In this course, we will address an algorithm problem that calculates the amount of water based on certain conditions using Kotlin. By tackling this problem, which is frequently featured in coding tests, you can develop algorithmic thinking and strengthen the fundamentals of Kotlin programming. This course will provide detailed explanations, including problem description, approach, code implementation, algorithm analysis, and optimization techniques.

Problem Description

You have an object with a flat bottom. The height information of this object can be represented as an array, where each index indicates the height at that position. After it rains on the object, write a program to calculate the amount of water that accumulates at each position.

Input

  • Integer N (1 ≤ N ≤ 1000): Size of the height array
  • Integer array heights (0 ≤ heights[i] ≤ 106): Height information at each position

Output

  • Print the total amount of water accumulated on the object

Example

Input:
5
0 1 0 2 1 0 1 3 2 1 2 1

Output:
6

In the above case, the object with a height of 1 at position 2 and an object with a height of 2 at position 3 trap water, resulting in a total of 6 units of water.

Approach

To solve this problem, you can use the following methodology:

  • Understand the structure where water collects in the lowest base.
  • Use two arrays to calculate the maximum height from the left and right, making it easy to compute the amount of water that can accumulate at each position.

Step 1: Create Maximum Height Arrays

First, create arrays to store the maximum height from both the left and the right for each position.

Step 2: Calculate Water Amount

Write a loop that iterates through each index to calculate the amount of water that can accumulate at that index.

Code Implementation

Now, let’s implement the code based on this approach.

fun calculateWaterVolume(heights: IntArray): Int {
    val n = heights.size
    if (n == 0) return 0

    // Left and right maximum height arrays
    val leftMax = IntArray(n)
    val rightMax = IntArray(n)

    // Calculate maximum height from left to right
    leftMax[0] = heights[0]
    for (i in 1 until n) {
        leftMax[i] = maxOf(leftMax[i - 1], heights[i])
    }

    // Calculate maximum height from right to left
    rightMax[n - 1] = heights[n - 1]
    for (i in n - 2 downTo 0) {
        rightMax[i] = maxOf(rightMax[i + 1], heights[i])
    }

    // Calculate the amount of water
    var totalWater = 0
    for (i in 0 until n) {
        totalWater += minOf(leftMax[i], rightMax[i]) - heights[i]
    }

    return totalWater
}

// Main function
fun main() {
    val heights = intArrayOf(0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)
    val result = calculateWaterVolume(heights)
    println("Total amount of water: $result")
}

Algorithm Analysis

The time complexity of this algorithm is O(N), where N is the length of the height array. We achieve this complexity by iterating through each index twice. Additionally, it requires O(N) space complexity as well, sufficient for the arrays used to store the maximum heights at each index.

Optimization Techniques

The above code can be further optimized to save space. By using pointers to directly calculate the maximum height at each index without using two arrays, the space complexity can be reduced to O(1).

fun calculateWaterVolumeOptimized(heights: IntArray): Int {
    val n = heights.size
    if (n == 0) return 0

    var left = 0
    var right = n - 1
    var leftMax = 0
    var rightMax = 0
    var totalWater = 0

    while (left < right) {
        if (heights[left] < heights[right]) {
            if (heights[left] >= leftMax) {
                leftMax = heights[left]
            } else {
                totalWater += leftMax - heights[left]
            }
            left++
        } else {
            if (heights[right] >= rightMax) {
                rightMax = heights[right]
            } else {
                totalWater += rightMax - heights[right]
            }
            right--
        }
    }

    return totalWater
}

Conclusion

In this course, we have tackled an algorithm problem for calculating the amount of water. This type of problem frequently appears in coding tests and is very helpful in building algorithmic thinking and foundational Kotlin programming skills. We also explored optimization techniques to minimize space complexity. I hope you learned a lot from this course.