Hello everyone! In this tutorial, we will take a close look at the basics of the C++ programming language and the algorithm problem-solving process through a problem of calculating the amount of water. Algorithm problems require not only writing simple code but also thinking about how to understand and interpret the problem. Therefore, we will cover the problem-solving approach, code writing, performance analysis, and optimization strategies in detail.
Problem Description
The overall definition of the problem is as follows: Given an array of heights, the task is to calculate how much water can accumulate in certain areas when it rains. This is widely known as the “Trapping Rain Water” problem, and there are various and interesting solutions available.
Example Problem
Let’s assume we are given a height array. For example, consider the following array:
{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
Given the above array, when it rains, water can accumulate as follows:
- Index 0: No water accumulated
- Index 1: No water accumulated
- Index 2: 1 unit of water
- Index 3: No water accumulated
- Index 4: 1 unit of water
- Index 5: 2 units of water
- Index 6: 1 unit of water
- Index 7: No water accumulated
- Index 8: 1 unit of water
- Index 9: 1 unit of water
- Index 10: 1 unit of water
- Index 11: No water accumulated
Thus, the total amount of accumulated water is 6 units.
Problem Approach
To solve the problem, we must first understand how water accumulates. The amount of water that can accumulate depends on the higher boundaries surrounding a specific index. For example, in order for water to accumulate at a position, there must be higher boundaries on both sides of that position, and the lower part of these two boundaries determines the height at which water can accumulate.
There are several methods to calculate this, and we will introduce two methods here:
- Two-pointer method
- DP (Dynamic Programming) method
Two-Pointer Method
The first approach uses the two-pointer method. This involves placing pointers on the left and right and calculating the amount of water based on the higher walls. This method can typically solve the problem by traversing the array only once, resulting in an O(n) time complexity.
Algorithm Explanation
- Place pointers at both ends of the array and initialize variables to store the maximum heights from the left and right.
- Repeat until the two pointers cross each other.
- If the current height of the left pointer is lower than the height of the right pointer, move the left pointer one step to the right and calculate the amount of trapped water using the difference between the stored maximum height.
- If not, move the right pointer one step to the left and perform a similar calculation.
Code Implementation
#include#include using namespace std; int trap(vector & height) { if (height.size() == 0) return 0; int left = 0, right = height.size() - 1; int left_max = 0, right_max = 0; int water_trapped = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= left_max) { left_max = height[left]; } else { water_trapped += left_max - height[left]; } left++; } else { if (height[right] >= right_max) { right_max = height[right]; } else { water_trapped += right_max - height[right]; } right--; } } return water_trapped; } int main() { vector height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}; cout << "Total water trapped: " << trap(height) << endl; return 0; }
Dynamic Programming Method
There is also a method using dynamic programming. This method proceeds based on a pre-calculated array of how much water can accumulate at each index. This method also has an O(n) time complexity.
Algorithm Explanation
- Determine the length of the integer array and create two arrays; one for the maximum height from the left and another for the maximum height from the right.
- Fill the left maximum height array. The maximum height at each index is set by selecting the greater value between the previous index’s maximum height and the current height.
- Similarly, fill the right maximum height array.
- Finally, the amount of trapped water at each index is determined based on the two maximum height arrays: min(left_max[i], right_max[i]) – height[i].
Code Implementation
#include#include using namespace std; int trap(vector & height) { if (height.size() == 0) return 0; int n = height.size(); vector left_max(n); vector right_max(n); int water_trapped = 0; // Calculate left maximum height left_max[0] = height[0]; for (int i = 1; i < n; i++) { left_max[i] = max(left_max[i - 1], height[i]); } // Calculate right maximum height right_max[n - 1] = height[n - 1]; for (int i = n - 2; i >= 0; i--) { right_max[i] = max(right_max[i + 1], height[i]); } // Calculate amount of trapped water for (int i = 0; i < n; i++) { water_trapped += min(left_max[i], right_max[i]) - height[i]; } return water_trapped; } int main() { vector height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}; cout << "Total water trapped: " << trap(height) << endl; return 0; }
Performance Analysis
Both approaches above have O(n) time complexity. However, if space complexity is important, the two-pointer method is more efficient. In contrast, the dynamic programming method requires an additional O(n) space, so care should be taken when memory usage is important.
Optimization Strategies
To maximize performance in C++ coding tests, always consider population size, array size, algorithm complexity, etc. Also, be mindful of compiler optimizations, reduce unnecessary variables, and pay attention to memory management.
Conclusion
In this tutorial, we learned about basic array handling and algorithm writing methods in C++ through the water trapping problem. By analyzing various approaches and the pros and cons of each method, we also explored how to optimize them. I hope the knowledge and experience gained in today’s coding tests will be very useful in the future.
Always be the one who practices and improves! Thank you.