Trapping Rain Algorithm Typescript

Managed to figure this out, unfortunately, I didn’t trap the job😅

I am very sarcastic and it may seem like I am beating myself up, well I am, a bit, but trust me I am good. I now know the solution. Don’t beat yourself up. Keep going, you will get it.

A couple of days ago I had a video chat interview with for a senior front end role. Needless to say, as the sub-title suggests, I didn’t get the job.

I feel I will write up an article about why I feel this ‘pass the algorithm type test’ is inherently flawed, but only once I get a job. Right now, instead of being all salty, I will explain how to get the correct answer. In the way, I understand, now*.

NOTE: There are faster run time complexity solutions but It’s Friday and won't binge Dark Season 1 with my Mr. It has been a long fight for the TV but this is my chance whilst she is bored of Friends, reruns.

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Solution

For example, Given [3, 0, 2, 0, 4], return 7.

The above image represented by array [3, 0, 2, 0, 4]. In this case, 7 units of rainwater (blue section) are being trapped. This is calculated by adding each unit of stored water at each index (position in the Array)

Water stored = 0 + 3 + 1 + 3 + 0 = 7

Easy right? Well, it took me 5 plus hours lone wolfing in my lab to wrap my head around this.

To show you who I answered it during the session, I took a sneak screenshot, think the dude heard but I bombed so I guess he was just stepping over another candidate carcass. They were all really nice by the way, and they said I was nice, which is nice, but a paycheck is nicer. So let see how you would trap your next job.

Don’t be fooled by the 2 passing tests, this algorithm has many tricks.

Steps I took to successfully botch my assessment

  1. *I had not seen this before, maybe I should have but shoulda woulda coulda…
  2. I noticed that I had to find the highest point, and use that to find the difference thus giving me the amount of water collected.
  3. This is where my brain stopped, and so did my chances

Lol

Seeing and working through the algorithm prior to the interview is the best way to be prepared, often it is the only way. Really peep, don’t beat yourself up if you cant think of this stuff on the fly — maybe you can I am the only dude who can’t, but then what you doing this far down this article) but that’s not true, so take it from me, you are not alone. I have been in the game 6 plus years professionally, I come from a design background, I wasn’t taught to think like this after I left high school. If you are the same, Hi, nice to meet you. Okay enough excuses, they only sound good to yourself. Let’s learn this Algo so we never get caught up again

Plain English Solution steps

So the trick here is to traverse (step through each element) the array from both sides, left and right, this will give you 2 arrays with values you can use against the original array.

If we use the above as an example, Given [3, 0, 2, 0, 4], return 7. This can be solved with my code attempt up top. Though correct it doesn’t solve for the case in which if the last column is smaller than the column before it the water must be allowed to run over and therefore no water is collected at that point. BOOOOM!

When the array is given as Arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], we get the resulting image (if drawn out, this is how you must think, visually). As you notice the first 4 elements are [0,1,0,2……] which means that there will only be 1 unit of water collected between Arr[1] and Arr[3] at position Arr[2].

This happens because the water must be allowed to overflow and is not counted as a unit if it does not have a column higher to support it on either side as in the images above. If you look at the end of the image a similar overflow is happening. This is essentially what tripped me up.

Thas, why my solution would work Test case 1 and 2 because the water is essentially enclosed by higher, peeks on either side.

Code Solution in Typescript

Step 1: Setup Initial Variables

Step 2: Loop from the left and get the highest points from the left’s perspective, this will make sense later I promise.

Step 3: Loop from the right and get the heights from the right perspective

Now that we have our 2 arrays with the height of each point from the left perspective and the right perspective. We can now check which one of the these is the smaller of the 2 and use that to get our leftover water unit at that index (position).

This is where I had to console.log things

If we line up the 2 arrays above each other we get a better picture of what is going on. Each array as stated before represents what the highest point is for that given point in the array. It does this by using the Math.max() method to check against the rightMax /leftMax and the height at that point in the array height[index]. This what gives us the arrays. Now if we place the original array underneath we can see each points calculation

Now subtract the height at each index from the minVal

Math.min(leftHeightCompareArr, rightHeightCompareArr) — height[i]

Step 4: Loop over original and minus the heights form the minVal at that index

When looping over it is important that we only consider the positive values, using a start forward ternary operator ( ‘check’ ? true : false ) we can ignore replace them with a 0 when adding up the water units.

Eureka!!!

Initially, I had pushed each value to an array and reduced them but that doesn’t work, you have to add the values + as you go along.

Full function thirstTrap()

Conclusion

Yeah that's it folk, will read through this and address and slip-ups in the morning but for now, that's a simple way to trap the rainwater.

Here are some nifty resources I found to help with this problem

Geeks For Geeks Always great

Stacks on Stacks, great explanation of runtime complexity, just scroll a bit

Thanks for reading, let me know if I can improve on anything and remember it's okay if you are not a Guru, you will get there. This a matter of time in the game, rather than timing the game.

Here is my personal repo for Data Strictures and Algorithms, which I will update as I run into more problems.

I build stuff