Apple Coding Interview Question! | Trapping Rain Water - Leetcode 42

dynamic programming, leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[amosreginaldjr.]

At this point every question on leetcode is “asked everytime”

[JustABigFan]

Way easier then calculating the surface area of a river whose banks are two hyperbolic functions.

[mussox]

I would count line by line bottom to top left to right using a state variable

[xandermichels]

I managed it by writing a code that goes from left to right then right to left taking the min value and it apparently managed to do it in half the time, super stoked by that

[DCTOR-ZED]

I believe you can reduce your space complexity from O(n) to O(1). Use two index variables starting at first and last index, two more for left and right max height (init at 0) and one for the running total. In a loop while left index<=right index you will do two sub loops. First sub loop, while the left index<=right index and the left max<=right max add any water for the value at the left index (if val at index is less than left max, add left max-val), set left max to the max of self and val at index, and increment left index. For the second sub loop, do the same for the right only decrementing the right index.

You are still O(n) for time, but you don't need temporary arrays the size of your data array.

[pigcake]

I figured you’d kinda go layer by layer and add the gaps between the walls, so subtracting one from every element of the array and for looping checking for an int and counting how many between the next int

[stopplanet]

There is a histogram area problem looks similar but totally different

[MajesticQT]

This is O(N) memory though, you can use a two pointer approach to make it O(1)

[erikoffenbach]

Nice riddle, For those who are interested I tried to solve it with ruby:

def calc_water_area(heights)
result = 0

do |left, right|
result +=
end

result
end


# Returns an array of indexes of the mountains in the array
# A mountain is where the left and right element are smaller than the current element
def find_mountains(array)
array.map.with_index do |height, index|
has_smaller_left = index == 0 || height > array[index - 1]
has_smaller_right = index == array.length - 1 || height > array[index + 1]
index if has_smaller_left && has_smaller_right
end.compact
end


# This expect an array, where no element is higher than the first and last element
def calc_valley_area(array)
max_water = [array[0], array.last].min
array.map.with_index do |height, index|
water_level = max_water - height
water_level = 0 if water_level < 0
water_level
end.sum
end

[illiakhomenko]

I solved this 20 mins before seeing this video! Used JS and 2 pointer + max/min described in the video

[DrCognitive]

I don't even know if i could answer the question. My brain would break on the "who cares" part.

[sunyfilip]

It would be much more obvious what you are saying if you'll be more specific. For example if you choose any position FROM INPUT, or at the end you get potential water OF THIS POSITION....cause at the end it sounds like this should be the result which is not and it was so confusing :D

[sri-varshan]

Yoo actually i got this question in my interview at Zoho I actually solved in 1 min just by finding the points where the current and prev value it should either increase or decrease if it change then mark the point after that i marked point find the rain water stored in between the marked pointes but finding the rectangle value and sub the sum of all value in btw the marked points

[odkwjbg]

MUCH Simpler solution: 1) find Pivot via max(heights, key=lambda pos: heights[pos]); 2) do 2 cycles TO Pivot from each end of the array 3) during each of 2 cycles, increase current_height OR add trapped water to counter

[REAZNx]

How are any of these leetcode questions useful in any way to a frontend/backend/fullstack dev position? 💀

[limken]

Still dont get how it works out or how you even get to the solution

[lesheq]

i came up with this solution:
def
water_amount = 0
for i in range(len(heights)):
try:
left = max(heights[:i])
except ValueError:
left = -1
try:
right = max(heights[i+1:])
except ValueError:
right = -1
if left != -1 and right != -1:
print(i, max(0, min(left, right) - heights[i]))
water_amount += max(0, min(left, right) - heights[i])

return water_amount

and i think it is both more effective, if someone disagrees let me know

[manakoi]

similar solution this time. you can avoid to instantiate 2 array: first get the max_right and then in the for loop you calculate the sum in a variable and keep the max_left in another

int RainWater(int[] height)
{
var maxRight = 0;
var maxRightValues = new int[height.Length];
for(int i=height.Length-1;i>=0;i--)
{
var h = height[i];
if (h > maxRight) maxRight = h;
maxRightValues[i] = maxRight;
}

var maxLeft = 0;
var water = 0;
for(int i=0;i<height.Length;i++)
{
var h = height[i];
if (h > maxLeft) maxLeft = h;
maxRight = maxRightValues[i];
var hMaxI = maxLeft > maxRight ? maxRight : maxLeft;
var waterI = hMaxI - h;
if (waterI > 0) water += waterI;
}
return water;
}

[evanrhildreth]

That question is very close to an old school signal processing algorithm.