Rainy New York

2 minute read

A few months ago I came across the challenge below:

“The Wall Street in New York is known for its breathtaking skyscrapers. But the raining season is approaching, and the amount of water that will fall over the buildings is going to be huge this year. Since every building is stuck to the buildings to its left and to its right (except for the first and the last one), the water can leak from a building only if the height of the building is higher than the height of the building to its left or to its right (the height of the edges of Wall Street is 0). All the buildings have the width of 1 meter. You are given the heights (in meters) of the buildings on Wall Street from left to right, and your task is to print to the standard output (stdout) the total amount of water (in cubic meters) held over the buildings on Wall Street.”

Example input: heights: [9 8 7 8 9 5 6]
Example output: 5

To address this problem, one can think of a segment of skyscrapers as a bar chart. The volume of water collected can be measured per bar and the final answer will be the sum of each portion of water at the top of the buildings. We can visualize it the following way:

To come up with the volume of water at each bar, we need to find out the tallest skyscraper to the left and to the right. The minimum tallest building will be the height to which we need to subtract the height of each building so we come up with the volume of water per skyscraper.

So, I used the R code below to compute a standard output for any given segment of buildings.

#creation of a vector with the heights of the buildings
tower <- c(9,8,7,8,9,5,6)

#function created to return the volume of water collected after raining, given the height of each building
stdout <- function(tower) {
 left_peak <- vector(mode = "numeric")
 right_peak <- vector(mode = "numeric")
 water_volume <- vector(mode = "numeric")

 #after the creation of the above empty vectors, the following line of code will return a vector with the height of the highest building on the left hand side of each position (starting with a 0)   
 for (n in 1:length(tower)) {
   if (n == 1) {
     left_peak[n] = 0
   } else {left_peak[n] = max(tower[1:(n-1)])
   }}

 #below, the code will return a vector with the height of the highest building on the right hand side of each position (starting with a 0)   
 for (n in length(tower):1) {
   if (n == length(tower)) {
     right_peak[length(tower)] = 0
   } else {right_peak[n] = max(tower[length(tower):(n+1)])
   }}

 #now, to calculate the volume of water we need to take the minimum peak between the left and right hand sides and subtract the tower height at each position. If the tower height is higher than the minimum peak, then no water will be collected.
 for (n in 1:length(tower)) {
   water_volume[n] = max(min(left_peak[n], right_peak[n]) - tower[n], 0)
 }

 #aftwerwards we just need to sum the volume of water accumulated at the top of each building
 return(sum(water_volume))
}

stdout(tower)

For further details and alternative solutions, please take a look at this Google Tech Talk by Guy Steele - Four Solutions to a Trivial Problem.

Tags:

Updated: