Our first optimization strategy.
We’ve been through brute force tactics since the beginning of this series. But from this point on, we’re also taking our attention to another strategy: optimization. This is something you must take notice of if you want to improve your coding skill because of its efficiency of resource usage.
Here’s part Ⅱ of the Trapping Rainwater challenge – Optimization Strategy. Before getting into this time’s main topic, let’s take a look at what I have done in the previous post, where we took advantage of the traditional brute force method.
As you may guess, since brute force loops through the x-axis both to the left and to the right, it consumes a lot of memory, which is not an ideal solution for an optimization. So, what we’re going to learn here is the optimization strategy.
This is our previous code.
In line 7, totalAmount is declared, and it doesn’t make logical sense to make any code-base modification to this variable since it only returns the ultimate value.
int totalAmount = 0;The same goes for the while-loop blocs that only return the calculated value.
while(r < a.length) {
if (a[r] > max_r) {
max_r = a[r];
}
r++;
}
while(l >= 0) {
if (a[l] > max_l) {
max_l = a[l];
}
l--;
}Logical thinking:
Here, refresh your memory with Road to Google’s second post – container with most water. In the post, we utilized the two-pointer technique. To get a visualizing idea, here’s an image from the post where two pointers, a and b, are looping through the array, just for an example.
And, here’s what we’re going to work on. PL on the left and PR on the other end of the line, and make them move inwards (image 04).
Through the inward loop from both sides, we need to collect data in each element by utilizing the previously mentioned formula:
cW = min(maxL, maxR) - cHLet’s take a look at our current brute force code again. Since we have r and l, we already have two pointers. The only difference is that both pointers move outwards, not inwards.
while(r < a.length) {
if (a[r] > max_r) {
max_r = a[r];
}
r++;
}
while(l >= 0) {
if (a[l] > max_l) {
max_l = a[l];
}
l--;
}As you can see: the brute force method makes the two pointers move outwards. this time around we have to work on the opposite.
Logical thinking time:
As shown in image 06, we have to control the two-pointer-loop flow inwards, and the timing at which the two collide with each other is the timing we accumulate the collected numbers with the formula.
Which pointer should we move fast?
Since the container is composed of two walls, which locates at both other ends of the line. In this case, 0 and 2. Compare 0 and 2, and ask yourself which is smaller than the other. Of course, it’s 0. So, we’ll move PL fast and make it scan through the numbers in the array first.
The first step:
maxLeft = 0
maxRight = 0
Do we need to try calculating the amount of water for this value? Or do we need to update our maxLeft? To start calculating through the array.
To make sure maxLeft is bigger than the current value, we have to think about the following steps.
The value can only have water above it if another wall exists next to it on the left side, whose value is bigger than itself.
And this logic can’t be applied to maxRight. Since maxRight is already bigger than the other end of the array, we know it is the wall on the right side.
And at this moment, we don’t know for sure if we have another wall next to maxLeft to the left side. And the only way we can figure it out is by comparing the current value, which is 0, with the maxLeft, which is also 0. 0 is no smaller than 0, so we’re sure now that the current value, 0, is the wall to the left.
The second step:
maxLeft = 0
maxRight = 0
PL moves to 1 and the program will compare 1 and the other end of line 2. 1 is still smaller, so we know 1 is the value we operate on.
What we need to figure out:
Is there a wall next to the current element?
Is the maxLeft (0) bigger than the current value (1)?
No, it’s not.
Then, there’s no possible way there’s a wall next to it, and there can’t be water above it.
Update maxLeft to 1.
The third step:
maxLeft = 1
maxRight = 0
PL moves to 0 and the program will compare 0 and the other end of line 2. 0 is still smaller, so we know 0 is the value we operate on.
What we need to figure out:
At this moment, we don’t have to apply the following formula to our method since the program already knows the maxLeft (1) is greater than the current value (0). We do the ‘min(maxL, maxR)’ calculation anyway, so we know the lesser of the two.
cW = min(maxL, maxR) - cHSo what we do is subtract the current value (0) from the maxLeft (1).
1 - 0 = 1From this point on, let’s keep track of total water = totalWater, which is 1 as of now.
The third step:
maxLeft = 1
maxRight = 0
totalWater = 1
PL moves to 2 and then we will compare the 2 and the other end of line 2. Both are equal and there’s no convincing reason to move the right side, which has no impact on the scanning process anyway. so we know the left 2 is the value we operate on.
Now ask yourself: do we calculate the water of update the maxLeft?
Compare the current value (2) and maxLeft (1).
There can’t be water above it, and we update the maxLeft to 2.
The fourth step:
maxLeft = 2
maxRight = 0
totalWater = 1
PL moves to 1 and then we will compare 1 and the other end of line 2. 1 is smaller, so we know 1 is the value we operate on.
Do we calculate the water of update the maxLeft?
Is the maxLeft (2) bigger than the current value (1)?
Yes, it is.
So what we do is subtract the current value (1) from the maxLeft (2).
2 - 1 = 1Add up 1 to the current totalWater, which is 2 as of now.
The fifth step:
maxLeft = 2
maxRight = 0
totalWater = 2
PL moves to 0 and then we will compare 0 and the other end of line 2. 0 is still smaller, so we know 0 is the value we operate on.
Do we calculate the water of update the maxLeft?
Is the maxLeft (2) bigger than the current value (0)?
Yes, it is.
So what we do is subtract the current value (0) from the maxLeft (2).
2 - 0 = 2Add up 2 to the current totalWater, which is 4 as of now.
The sixth step:
maxLeft = 3
maxRight = 0
totalWater = 4
PL moves to 3 and then we will compare 3 and the other end of line 2. 3 is greater, so we know 2 (the right side) is the value we operate on.
The seventh step:
maxLeft = 3
maxRight = 2
totalWater = 4
Now, the right side is moving inwards. PL moves to 1 and then we will compare 1 and 3. 1 is smaller, so we know 1 is the value we operate on.
Now we update maxRight to 2.
Do we calculate the water of update the maxRight?
Is the maxRight (2) bigger than the current value (1)?
Yes, it is.
So what we do is subtract the current value (1) from the maxRight (2).
2 - 1 = 1Add up 1 to the current totalWater, which is 5 as of now.
The eighth step:
maxLeft = 3
maxRight = 2
totalWater = 5
PL moves to 0 and then we will compare 0 and 3. 1 is smaller, so we know 0 is the value we operate on.
Do we calculate the water of update the maxRight?
Is the maxRight (2) bigger than the current value (0)?
Yes, it is.
So what we do is subtract the current value (0) from the maxRight (2).
2 - 0 = 2Add up 2 to the current totalWater, which is 7 as of now.
The ninth step:
maxLeft = 3
maxRight = 2
totalWater = 7
PL moves to 1 and then we will compare 1 and 2. 1 is smaller, so we know 1 is the value we operate on.
Do we calculate the water of update the maxRight?
Is the maxRight (2) bigger than the current value (1)?
Yes, it is.
So what we do is subtract the current value (1) from the maxLeft (2).
2 - 1 = 1Add up 1 to the current totalWater, which is 8 as of now.
Finally…
Now we’ve done the calculation since the PL and PR now bumped up against each other.
Coding implementation:
Here, let’s implement what we’ve learned into actual coding. The following image (image 08) shows you step-by-step instructions.
Declare variables.
The r is declared as ‘height.length – 1’ because the array starts from 0, so the other end of the array must be array.length – 1.
int l = 0;
int r = height.length - 1;
int total = 0;
int max_l = height[l] ,
max_r = height[r];while (l<r) {
//Identify a pointer with a lesser value.
if(height[l]<= height[r])
{
//Is this pointer value greater or equal to the max to the side?
if(height[l]>max_l)
{
//If Yes → update max on the side
max_l = height[l];
}
else
{
//If No → get water for the pointer value and add it up to the total
int curr = max_l - height[l];
total = total + curr;
}
l++;
}
else
{
if (height[r]>max_r)
{
max_r = height[r];
}
else
{
int curr = max_r - height[r];
total = total + curr;
}
r--;
}
}
return total;
}Actual code:
Finally, here’s the actual code that can work.
import java.io.*;
class trappingRainwaterOptimazation {
public static int waterCalc(int[] height)
{
int l = 0;
int r = height.length - 1;
int total = 0;
int max_l = height[l] , max_r = height[r];
while (l<r) {
if(height[l]<= height[r])
{
if(height[l]>max_l)
{
max_l = height[l];
}
else
{
int curr = max_l - height[l];
total = total + curr;
}
l++;
}
else
{
if (height[r]>max_r)
{
max_r = height[r];
}
else
{
int curr = max_r - height[r];
total = total + curr;
}
r--;
}
}
return total;
}
public static void main(String[] args) {
int a[] = { 0,1,0,2,1,0,3,1,0,1,2 };
System.out.println(waterCalc(a));
}
}Afterthoughts:
Okay, so we’ve been through the optimization strategy. And this method is not only beneficial for you to improve your coding skill, but it’s also quite useful when you want to take advantage of your limited resources.
Anyways, keep coding and keep improving our skills!