Problem Statement
Rain Water Collector
You are an urban planner designing a new city district. The district consists of buildings of various heights arranged in a row. When it rains, water can get trapped between the buildings.
Given an array of non-negative integers representing the height of each building, calculate how much rainwater can be trapped between the buildings after a heavy rainfall.
Each building has a width of 1 unit, and the water level between any two buildings is determined by the height of the shorter building.
Examples
Example 1:
Input: heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Explanation: The trapped water is represented by the blue areas in the diagram. The total amount of trapped water is 6 units.
Example 2:
Input: heights = [4, 2, 0, 3, 2, 5]
Output: 9
Explanation: The trapped water is 9 units: 2 units between buildings of height 4 and 3, 3 units between buildings of height 3 and 5, and 4 units between buildings of height 4 and 5.
Constraints
- The number of buildings (length of the array) is between 1 and 2 × 10^4.
- The height of each building is between 0 and 10^5.
- The buildings are arranged in a straight line with no gaps between them.
Problem Breakdown
To solve this problem, we need to:
- For each position, the amount of water that can be trapped depends on the minimum of the maximum heights to its left and right.
- We need to find, for each position, the highest building to its left and the highest building to its right.
- The problem can be solved using dynamic programming, two pointers, or a stack-based approach.
- The key insight is that water can only be trapped if there are taller buildings on both sides.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Rain Water Collector
You are an urban planner designing a new city district. The district consists of buildings of various heights arranged in a row. When it rains, water can get trapped between the buildings.
Given an array of non-negative integers representing the height of each building, calculate how much rainwater can be trapped between the buildings after a heavy rainfall.
Each building has a width of 1 unit, and the water level between any two buildings is determined by the height of the shorter building.
Examples
Example 1:
The trapped water is represented by the blue areas in the diagram. The total amount of trapped water is 6 units.
Example 2:
The trapped water is 9 units: 2 units between buildings of height 4 and 3, 3 units between buildings of height 3 and 5, and 4 units between buildings of height 4 and 5.
Problem Breakdown
Constraints:
- The number of buildings (length of the array) is between 1 and 2 × 10^4.
- The height of each building is between 0 and 10^5.
- The buildings are arranged in a straight line with no gaps between them.
Key Insights:
For each position, the amount of water that can be trapped depends on the minimum of the maximum heights to its left and right.
We need to find, for each position, the highest building to its left and the highest building to its right.
The problem can be solved using dynamic programming, two pointers, or a stack-based approach.
The key insight is that water can only be trapped if there are taller buildings on both sides.
Real-World Application
This problem has several practical applications:
Urban Planning
Calculating water accumulation in urban areas for drainage system design.
Hydrology
Modeling water collection in natural terrain for flood prediction and management.
Architecture
Designing rooftops and structures to manage rainwater efficiently.