Hard level of brute force tactics.
So, here’s one of the hardest forms of brute force techniques that you may need to solve the challenge. But what’s interesting here is that you can take advantage of the previous challenges; experiences and knowledge. Let’s try!
So, this is the third trial of Road to Google. And this time, you’ll be challenged to solve the Trapping Rainwater problem. Compared to the previous two challenges, this one is much harder and may force you to train your brain muscle. But don’t be afraid, I’m still on the journey to improve my skills. Okay, without further adieu, let’s dive into it!
Question:
Given an array of integers representing an elevation map where the width of each bar is 1, return how much rainwater can be trapped.
The given array:
[0,1,0,2,1,0,3,1,0,1,2]
Explanation:
Phew… okay, this time’s question is also a bit complicated and maybe a bit challenging to visualize the logical structure of what the question asks you for.
Here, the following images visualize what this challenge is asking you for.
Elevation map:
In this challenge, the keyword is the elevation map. What is it? Well, it’s simply the height of each number in the array. Just take a look at image 01.
And his challenge is asking you to “return how much rainwater can be trapped“. So, let’s visualize it again. The blue-colored blocks in image 02 represent the returning number from the array: the amount of water than can be trapped inside the array blocks.
Now, can you see what this challenge is about, right? Again, it’s a lot harder than the previous ones, but you can take advantage of the skills you gained through the previous challenges.
Abstract thinking:
First off, to solve this challenge, you can certainly take advantage of the knowledge that helped you solve the previous one. For a starter, the amount of trapped water inside array numbers, 1 and 2, in image 03 can never exceed the lesser number of the two. And this is the similarity to the previous one.
However, what makes this challenge a bit harder is this part, for example. Let’s give our focus on the range in the array from 2,1,0,3 as shown in image 04. 2 determines the height of the water that can go up to, while 3 is the bigger of the two as well as the other end of the container. As you can guess, what makes this challenge a lot harder than the previous one is the part of 1 that cut into the trapped water bloc.
The same goes for the following image 05. 2 determines the height of water than can go up to while the 3 composes the other end of the container. And the additional two 1s inside the block reduce the amount of water the container can hold.
To grasp the whole idea even further, let’s take a look at another example in image 06. Think about how much water can be above the 0 surrounded by a red circle here.
Compared the two biggest array number 5 and 4, 4 can be the height of the container. So, the amount of water that can be above 0 in image 07 is 4 – subtract 4 (the maximum height of water ) from 0.
Okay, here’s another example. Take a look at 3 in image 08. The same as the previous sample, the amount of water block above 3 is 1 (4 – 3 = 1).
Mathematical formula:
Here, let’s put this knowledge into a mathematical formula:
cW: current water.
maxL: max number to the left
maxR: max number to the Right
cH: current height
And here’s the formula
cW = min(maxL, maxR) – cH
What we do:
With the formula, we can calculate the amount of water every single element in the array can hold and keep track of each amount of water, adding them all up to find the answer.
Logical visualization:
From this point, let’s visualize the aforementioned logic.
1st: set variables
totalAmount = 0
maxL = 0
maxR = 0
2nd: for-loop visualization:
P starts from 0 on the x-axis.
Nothing is on the left, so the maxL stays at 0.
On the left side, there’s 1, and 1 is greater than 0.
So the maxR is replaced by 1.
Then, there’s 0, and 0 is not greater than 1.
So the maxR stays at 1.
Then it continues the for-loop until the end of the array…
Up until the end of the array, 3 is the biggest number, so maxR will eventually be replaced by 3.
totalAmount = 0
maxL = 0
maxR = 3
And here’s the formula:
cW = min(maxL, maxR) – cH
↓
cW = min(0, 3) – 0
↓
0 = 0 – 0
So, the first 0’s amount of water is 0.
And a new for-loop begins from 1.
And variables are all initialized again.
totalAmount = 0
maxL = 0
maxR = 0
0 is on the left, so the maxL stays at 0.
Up until the end of the array, 3 is the biggest number, so maxR will eventually be replaced by 3.
totalAmount = 0
maxL = 0
maxR = 3
And here’s the formula:
cW = min(maxL, maxR) – cH
↓
cW = min(0, 3) – 1
↓
-1 = 0 – 1
The answer is -1, and we have to skip it if the number became anything below 0.
And a new for-loop begins from 0 next to it.
1 is on the left, so the maxL is replaced by 1.
totalAmount = 0
maxL = 1
maxR = 3
Up until the end of the array, 3 is the biggest number, so maxR will eventually be replaced by 3.
totalAmount = 0
maxL = 1
maxR = 3
And here’s the formula:
cW = min(maxL, maxR) – cH
↓
cW = min(1, 3) – 0
↓
1 = 1 – 0
The answer is 1, so the water above the number is 1.
And when you add the number to totalAmount, it becomes totalAmount = 1.
And the P moves to 2 next to the previous 0.
And keep in mind that totalAmount now becomes 1, and the numbers that are going to add up to totalAmount will be added to the current number.
totalAmount = 1
maxL = 0
maxR = 0
Coding solution:
Here’s the coding solution the embodies the aforementioned logic.
This is the executed result.
In addition to that, here’s a more advanced and polished version of the previous one.
Afterthoughts:
So, how did you like it? Was it hard for you? Anyways, just like always, I’ll try the same challenge in other languages as well in later posts.
See you soon!!