Skip to content

Instantly share code, notes, and snippets.

@oralokan oralokan/gist:107958531b3e33062bc5 Secret
Last active Dec 27, 2015

Embed
What would you like to do?
Response to mkozakov's gist
# This is my solution to the problem posted by mkozakov.
# It is a single pass solution.
# It is based on a very simple observation.
# Let us define a 2D Grid such that the number of columns is equal to
# the number of values in the input array (which I call landscape)
# and the number of rows is equal to the greatest value in the same array.
# Each square in the grid is either a solid block, or free space that
# can be filled with water.
# The simple observation is, the conditions for a square to be occupied
# by water are:
# - It has to be free space to begin with
# - There has to be a solid block on either side
# of it at the same height (not necessarily adjacent).
# We simply test each of the free space squares according to the
# condition stated above, and increment a counter
def calculateWaterVolume(landscape):
gridHeight = max(landscape)
gridWidth = len(landscape)
# We create a 2D grid with 0-1 values
# 1 corresponds to a solid block
# 0 corresponds to empty space
grid = []
for i in range(gridWidth):
grid.append([])
for j in range(gridHeight):
if (j < landscape[i]):
grid[i].append(1)
else:
grid[i].append(0)
count = 0 # The counter for the number of squares filled with water
# Note that the first and last columns cannot hold water.
# Hence, we only need to consider columns 1, ... ,gridWidth-2
for i in range(1, gridWidth-1):
# As for rows, there is no need to consider the solid blocks
for j in range(landscape[i], gridHeight):
# The free space will be occupied by water if and only if
# there exists a solid block at the same height to the left AND
# to the right.
boundedLeft = False
for k in range(0,i):
if grid[k][j] == 1:
boundedLeft = True
boundedRight = False
for k in range(i+1, gridWidth):
if grid[k][j] == 1:
boundedRight = True
if boundedLeft and boundedRight:
count += 1
return count
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.