Java Coding Test Course, Calculating the Amount of Water

Algorithm problems are very important in coding tests. In particular, the ability to solve problems using Java is one of the skills that many companies require. In this article, I will explain in detail the topic of “Calculating the Amount of Water.” Through this problem, we will explore the process of finding an algorithmic solution and implementing it in Java step by step.

Problem Description

You have an array of given heights. Each index represents a block, and the value at each index represents the height of the block. You need to write a program to calculate the amount of water that can be stored due to the given rain in this array.

For example, if the given array is [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], you need to find the amount of water stored in the array.

Approach to Solving the Problem

There are several approaches to solving this problem, but the most intuitive way is to use the two-pointer approach. By using two pointers that move from both ends of the array toward the center, we can calculate the amount of water that can be stored at each index.

Step 1: Understanding the Problem

The amount of water stored at each index is determined by the height of the tallest block to the left and right of that index. Therefore, the amount of water stored is
min(left max height, right max height) - current block height. If this value is negative, it means no water is stored, so it can be set to 0.

Step 2: Designing the Algorithm

To design the algorithm, we will set up the following steps:

1. Calculate the length of the array and handle exceptions for the user.
2. Start from both ends and set up two pointers.
3. Track the maximum height at each pointer.
4. Repeat until the two pointers meet.
5. Calculate the amount of water stored at each step.

Step 3: Implementing the Code

Now, based on the above design, let’s implement the Java code.

public class WaterTrapping {
    public static int calculateWater(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int totalWater = 0;

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

        return totalWater;
    }

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("Amount of water stored: " + calculateWater(height) + " units");
    }
}
        

Step 4: Explaining the Code

The key part of the code is the while (left < right) loop. This loop continues until the two pointers cross each other.

• If the left pointer is less than the right pointer: Update the maximum height on the left or, if the current value is lower, calculate the amount of water that can be stored.
• If the right pointer is less than the left pointer: Update the maximum height on the right or calculate the amount of water that can be stored.

In this way, the loop continues until the two pointers meet, summing up the total amount of water stored.

Conclusion

Today, we learned about the algorithm frequently presented in coding tests through the problem of "Calculating the Amount of Water." The algorithm using two pointers provides efficient space utilization and time complexity, so it is commonly used in actual coding tests, and it is important to practice it thoroughly.

I hope you continue with deeper learning through various additional examples and complex test cases. May this problem enhance your algorithmic thinking.