I tackled the 𝗧𝗿𝗮𝗽𝗽𝗶𝗻𝗴 𝗥𝗮𝗶𝗻 𝗪𝗮𝘁𝗲𝗿 problem during my Microsoft interview, and this is one of the most famous interview problem! Let me break it down for you in a way that’s simple yet impactful.
𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝗶𝗻 𝗦𝗶𝗺𝗽𝗹𝗲 𝗧𝗲𝗿𝗺𝘀
Imagine you’re looking at a skyline of buildings represented as an array of heights. After a heavy rain, water gets trapped between these buildings. Your goal is to calculate the total amount of water trapped.
𝗘𝘅𝗮𝗺𝗽𝗹𝗲:
Input: height = [0,1,0,2,1,0] Output: 6
Explanation: The total amount of water trapped between the bars is 6 units.
𝗟𝗲𝗲𝘁𝗖𝗼𝗱𝗲 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝗟𝗶𝗻𝗸:
Trapping Rain Water -
https://lnkd.in/ge2NbZac
𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡𝐞𝐬 𝐭𝐨 𝐒𝐨𝐥𝐯𝐞 𝐈𝐭
𝟭. 𝗕𝗿𝘂𝘁𝗲 𝗙𝗼𝗿𝗰𝗲
This is the most straightforward way to solve the problem. For each building (or bar), you calculate how much water it can trap by finding the tallest building to its left and right. The trapped water above that building is determined by the smaller of these two heights minus the height of the current building.
However, this approach is inefficient because it repeatedly scans the array for every building. It works but takes O(n²) time-definitely not ideal for large inputs.
𝟮. 𝗗𝘆𝗻𝗮𝗺𝗶𝗰 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴
Dynamic Programming optimizes the brute force approach by precomputing values. Instead of scanning the array repeatedly for each building, we create two arrays:
left_max: Stores the maximum height to the left of each building.
right_max: Stores the maximum height to the right of each building.
Once these arrays are computed, calculating trapped water becomes a simple matter of using these precomputed values. This brings down the time complexity to O(n) while using extra space for the arrays (O(n)).
𝟯. 𝗧𝘄𝗼 𝗣𝗼𝗶𝗻𝘁𝗲𝗿𝘀 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵
This is where things get really interesting! The two-pointers technique eliminates the need for extra space and solves the problem in O(n) time with O(1) space complexity.
𝗛𝗲𝗿𝗲’𝘀 𝗵𝗼𝘄 𝗶𝘁 𝘄𝗼𝗿𝗸𝘀:
Start with two pointers: one at the beginning (left) and one at the end (right) of the array.
Maintain two variables: left_max and right_max, which track the tallest buildings encountered so far from both sides.
Move the pointers inward based on which side has a smaller maximum height. At each step, calculate how much water can be trapped above the current building using the smaller maximum height.
This approach is elegant and highly efficient-it’s often preferred in interviews because it demonstrates mastery over optimization techniques.
𝗪𝗵𝘆 𝗧𝗵𝗶𝘀 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝗜𝘀 𝗣𝗼𝗽𝘂𝗹𝗮𝗿 𝗶𝗻 𝗜𝗻𝘁𝗲𝗿𝘃𝗶𝗲𝘄𝘀?
The Trapping Rain Water problem is a classic example of testing your ability to:
Understand a problem intuitively.
Develop multiple solutions (brute force vs optimized).
Optimize both time and space complexity.
Implement techniques like Dynamic Programming or Two Pointers efficiently.