Difficulty: Hard, Asked-in: Google, Microsoft, Amazon
Key takeaway: A popular interview problem to learn time and space complexity optimization using various approaches. All the solutions are worth exploring, where the two-pointers approach helps to design an efficient solution in O(n) time and O(1) space.
Given n non-negative integers representing an elevation map where the width of each tower is 1. Write a program to compute how much water it can trap after raining.
Example 1
Input: height[] = [2, 0, 1, 0, 2], Output: 5
Explanation: Trapped water = 2 x 1 + 1 x 1 + 2 x 1 = 5 (Area of the blue region in the following diagram)
Example 2
Input: height[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], Output: 6
Explanation: Trapped water = 1 x 1 + 1 x 1 + 2 x 1 + 1 x 1 + 1 x 1 = 6 (Area of the blue region in the following diagram)
Solution Idea
One basic idea would be to traverse the height[] array and add the water trapped at each tower. The critical question is: how do we find the amount of water trapped by any tower height[i]? Let's think!
Observing closely, the trapped water by tower height[i] will be bounded by the maximum tower height on the left and right sides. The water trapped at height[i] = min (max tower height on the left side, max tower height on the right side) - height[i].
Note: We also include the current height in the calculation for finding the max height on the left and the right side. Why? The idea is simple: Suppose height[i] is the maximum height in the array, then water trapped at that height would be 0. So if we include the current height in finding the left and right max:
Solution Steps
We run a loop from j = i to 0 and find the maximum height of the tower on the left side. We store this value in the variable leftMaxHeight.
for(int j = i; j >= 0; j = j - 1)
leftMaxHeight = max(height[j], leftMaxHeight)
Similarly, we run a loop from j = i to n - 1 and find the maximum height of the tower on the right side. We store this value in the variable rightMaxHeight.
for(int j = i; j < n; j = j + 1)
rightMaxHeight = max(height[j], rightMaxHeight)
Now using the above formula, we calculate the amount of water trapped by height[i] and add it to the variable trappedWater.
trappedWater = trappedWater + min(leftMaxHeight, rightMaxHeight) - height[i]
Solution Pseudocode
int rain_water_trapping(int height[], int n)
{
if(n <= 2)
return 0
int trappedWater = 0
for(int i = 0; i < n; i = i + 1)
{
int leftMaxHeight = 0 , rightMaxHeight = 0
for(int j = i; j >= 0; j = j - 1)
leftMaxHeight = max(height[j], leftMaxHeight)
for(int j = i; j < n; j = j + 1)
rightMaxHeight = max(height[j], rightMaxHeight)
trappedWater = trappedWater
+ min(leftMaxHeight, rightMaxHeight) - height[i]
}
return trappedWater
}
Solution analysis
Solution Idea
Can we improve the efficiency further and solve the problem in O(n) time? Is it possible to get rid of the inner loops for finding the leftMaxHeight and rightMaxHeight? If the values of leftMaxHeight and rightMaxHeight are known for each tower height[i], we can solve this problem in a single scan of the height[] array. But how can we do this? Let's think!
One idea would be to do some pre-processing to calculate both values for each tower and store them in two separate extra memory of size n. Suppose we take left[n] and right[n] to store the values where left[i] = leftMaxHeight of the tower height[i], right[i] = rightMaxHeight of the tower height[i]. Can we store the values of both arrays in O(n) time? Here is an idea:
Solution Steps
Now we initialize the left[0] with height[0] and run a loop from i = 1 to n - 1 to store the remaining values in the left[] array. At each iteration i, we store the max element that occurred up to that point in left[i].
left[0] = height[0]
for(int i = 1; i < n; i = i + 1)
left[i] = max(left[i - 1], height[i])
Similarly, we initialize the right[n - 1] with height[n - 1] and run a loop from i = n - 2 to 0 to store the remaining values in the right[] array. At each iteration, we store the max element that occurred up to that point in the right[i].
right[n - 1] = height[n - 1]
for(int i = n - 2; i >= 0; i = i - 1)
right[i] = max(right[i + 1], height[i])
Now, we traverse the height[] array and calculate the total amount of water.
int trappeWater = 0
for(int i = 0; i < n; i = i + 1)
trappedWater = trappedWater + min(left[i], right[i]) - height[i]
Solution Pseudocode
int rain_water_trapping(int height[], int n)
{
if(n <= 2)
return 0
int left[n], right[n]
left[0] = height[0]
for(int i = 1; i < n; i = i + 1)
left[i] = max(left[i-1], height[i])
right[n-1] = height[n-1]
for(int i = n-2; i >= 0; i = i - 1)
right[i] = max(right[i+1], height[i])
int trappeWater = 0
for(int i = 0; i < n; i = i + 1)
trappedWater = trappedWater + min(left[i], right[i]) - height[i]
return trappedWater
}
Solution Analysis
Solution Idea
Can we solve this problem in a single scan of the height[] array? Let's explore.
Did we observe some patterns? The idea would be to track the area confined between the current tower and all the previous smaller towers in a sequence. We can use a stack to track the indices of the previous smaller towers. (Think!)
Solution Steps
If we found a current tower height[i] larger than the tower at the top of the stack, we can say that the tower at the top is confined between the current tower and a previous tower in the stack. Hence, we pop the value from the stack and add water trapped between towers to the total water trapped. We can continue this step in a loop until we find the current tower smaller than the tower at the top of the stack or the stack becomes empty.
Solution Pseudocode
int rain_water_trapping(int height[], int n)
{
int trappeWater = 0, curr = 0
stack S
while (curr < n)
{
while (!S.empty() && height[curr] > height[S.top()])
{
int topTower = S.Pop()
if (S.empty())
break
int regionLength = curr - S.top() - 1
int regionHeight = min (height[curr], height[S.top()])
- height[topTower]
trappedWater = trappedWater + regionLength * regionHeight
}
S.push(curr)
curr = curr + 1
}
return trappedWater
}
Solution Analysis
We are doing a single traversal of the height[] array. In the worst case, we are processing each tower twice using a stack i.e. one push() and one pop() operation. (Think!) Both push() and pop() operations take O(1) time in the worst case. So, time complexity = O(n).
In the worst-case, the stack can take up to n elements. Space complexity = O(n)
Note: If(height[i] > height[S.top()]), then the tower at the top of the stack is smaller than the previous tower in the stack and current tower height[i]. In such a scenario, it would form a colored rectangular region and trapped water is equal to the area of that region.
Solution Idea
In the last two approaches, we are using extra spaces to get the solution. Can we solve this problem in a single scan without using extra space? Let's explore!
Based on the formula used in the 2nd approach, the water trapped by any tower depends on the minimum of maximum height of towers on both sides. So instead of maintaining two arrays of size n for storing leftMaxHeight and a rightMaxHeight, can we think of maintaining two variables to store the maximum till a given point? Think!
Suppose we search from both the left and right end by maintaining two pointers left and right separately. If there is a larger tower at the right end, then the water trapped would be dependent on the tower's height in the direction from left to right. Similarly, if the tower at the right end is smaller, then the water trapped would be dependent on the tower's height in the direction from right to left. Think!
We first calculate the water trapped on smaller elements out of height[left] and height[right], then move the pointer associated with the smaller element. We move the pointers till the left doesn't cross the right. In terms of an analogy, we can think of height[left] and height[right] as a wall of a partial container where we fix the higher one and flow water from the lower part. Think!
Solution Steps
We also Initialise variables trappedWater, leftMaxHeight, and rightMaxHeight.
int trappedWater = 0
int leftMaxHeight = 0, rightMaxHeight = 0
int left = 0, right = n - 1
Now we run a loop to scan the array i.e. while (left <= right)
if (height[left] < height[right])
{
if (height[left] > leftMaxHeight)
leftMaxHeight = height[left]
else
trappedWater = trappedWater + leftMaxHeight - height[left]
left = left + 1
}
if (height[left] > height[right])
{
if (height[right] > rightMaxHeight)
rightMaxHeight = height[right]
else
trappedWater = trappedWater + rightMaxHeight - height[right]
right = right - 1
}
Solution Pseudocode
int rain_water_trapping(int height[], int n)
{
int trappedWater = 0
int leftMaxHeight = 0, rightMaxHeight = 0
int left = 0, right = n - 1
while (left <= right)
{
if (height[left] < height[right])
{
if (height[left] > leftMaxHeight)
leftMaxHeight = height[left]
else
trappedWater = trappedWater + leftMaxHeight - height[left]
left = left + 1
}
else
{
if (height[right] > rightMaxHeight)
rightMaxHeight = height[right]
else
trappedWater = trappedWater + rightMaxHeight - height[right]
right = right - 1
}
}
return trappedWater
}
Solution Analysis
Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Please write comments if you find an error or you want to share more insights about the topic. Enjoy learning, Enjoy coding, Enjoy algorithms!
Given a string S[], write a program to sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. If two characters have the same frequency, whichever occurs earliest in S, must come first. In other words, the sorting must be stable.
Given a 2-dimensional matrix, print the elements in spiral order. We can imagine the spiral traversal as an ordered set of matrix segments with horizontal and vertical boundaries, where both boundaries are reduced by one at each step. This is a good matrix problem to learn problem-solving using iteration and recursion.
Given an array X[] of n integers, return true if and only if it is a valid mountain array. The array X[] is a mountain array if and only if n >= 3 and there exists some i with 0 < i < n - 1 such that: X[0] < X[1] <...X[i-1] < X[i] and X[i] > X[i+1] > ...> X[n - 1]. In other words, we call the array mountain array when the array is strictly increasing and then strictly decreasing.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.