Skip to content

Instantly share code, notes, and snippets.

@loicginoux
Created December 27, 2019 21:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save loicginoux/c9b43500c672da6e1fb58afdd2356cc9 to your computer and use it in GitHub Desktop.
Save loicginoux/c9b43500c672da6e1fb58afdd2356cc9 to your computer and use it in GitHub Desktop.
Daily Coding Problem: Problem #30 [Medium]
# You are given an array of non-negative integers that represents a two-dimensional elevation map where each element is unit-width wall and the integer is the height. Suppose it will rain and all spots between two walls get filled up.
# Compute how many units of water remain trapped on the map in O(N) time and O(1) space.
# For example, given the input [2, 1, 2], we can hold 1 unit of water in the middle.
# Given the input [3, 0, 1, 3, 0, 5], we can hold 3 units in the first index, 2 in the second, and 3 in the fourth index (we cannot hold 5 since it would run off to the left), so we can trap 8 units of water.
# Solution:
# we run level after level, starting by level 1 and finishing at last level, the highest wall
# for each level we run through the array
# when we discover a wall we can start keeping bucket of water
# when we get en empty space we fill one bucket of water
# when we find another wall we bank, all water in "waiting list"
# will indeed be kept between 2 walls
def get_water_stored(arr)
max = 1
j = 1
validated = 0
while j <= max
p "j: #{j}, max:#{max}"
waiting_list = 0
start_filling = false
arr.each do |wall|
max = wall if wall > 0
if wall >= j
validated += waiting_list
waiting_list = 0
start_filling = true
elsif start_filling
waiting_list += 1
end
p "wall: #{wall} - wl #{waiting_list} - valid: #{validated}"
end
j += 1
end
validated
end
get_water_stored([3,0,1]) == 1
get_water_stored([1,0,3]) == 1
get_water_stored([3,0,1,3,0,5]) == 8
get_water_stored([3,0,0]) == 0
get_water_stored([0,1,3,1,0]) == 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment