Problem 31: Maxium Rainwater Trapping[Microsoft]

Maximization, Problem Framing, Forward and Backward Passes

How it going my subs,

Today’s question is a very interesting question asked by a lot of firms (especially MS). It is a must for especially my more senior subscribers, since this is a problem that doesn’t require a lot of esoteric knowledge, but does require very good problem solving and recognition skills.

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.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

You can find this problem as Leetcode 42. The optimal solution will be shared with the premium subscribers tomorrow. Make sure you like this post to help the newsletter grow.

You can test your solutions over here

Consider filling out this survey. This helps me understand you better and will allow me to improve the content: Link: https://forms.gle/XfTXSjnC8W2wR9qT9

Insane ROI

Struggling to Prepare for Coding Interviews? Stuck on Leetcode Questions? Too busy to go through the endless resources available online? Subscribe to Coding Interviews Made Simple, a newsletter to help you succeed with your newsletter. Using techniques developed through my proven track record of mentoring people with their interviews, I will help you ace your FAANG/MAMAA (and other Software Engineering) interviews. Get 20% for a full year using this special offer.

Happy Prep. I’ll see you at your dream job.

The rainwater harvester,

Devansh <3

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75