# Count Snow Units Captured between the Hills asked in GS [Coding Challenge]

Note: This coding challenge was asked in Goldman Sach coding round and in many other technical job interviews.

Given an array of non-negative integers representing the elevations from the vertical cross-section of a range of hills, determine how many units of snow could be captured between the hills.

Example:

See the example array and elevation map below.

Output: In this example, 13 units of snow (*) could be captured.

This problem is similar to the “maximum level of water it can trap after the rain”.

#### Explanation with algorithm:

• Create array left and save all the local current maxima while traversing from left to right.
• Create an array right and save all the local current maxima while traversing from right to left.
• find `min(left[i], right[i]) - arr[i]` for each element.
• Cacualte the sum form resultant array.

#### Python Solution

We are implementing above algorithm using Python programming.

Prerequisite:

```def computeSnowpack(arr):
# Todo: Implement computeSnowpack

len_arr = len(arr)
left = [arr]*len_arr
left_max = arr
for i in range(1, len_arr):
left_max = left_max if left_max>arr[i] else arr[i]
left[i] = left_max

right = [arr[-1]]*len_arr
right_max = arr[-1]
for i in range(len_arr-2, -1, -1):
right_max = right_max if right_max>arr[i] else arr[i]
right[i] = right_max

sum = 0
for i in range(len_arr) :
sum += min(left[i], right[i]) - arr[i]

return sum

def doTestsPass():
""" Returns True if all tests pass. Otherwise returns False. """
tests = [
[[2, 1, 3, ], 1],
[[0,1,3,0,1,2,0,4,2,0,3,0], 13],
[[2,1,3,0,1,2,0,4,2,0,3,0], 14],
]

for test in tests:
if not (computeSnowpack(test) == test):
return False
return True

if __name__ == "__main__":
if( doTestsPass() ):
print( "All tests pass" )
else:
print( "Not all tests pass")```

Complexity:

• The time complexity of this algorithm is O(n).
• The space complexity of this algorithm is O(n).

Similar coding challenges asked in Goldman Sachs

If you have any other solution or if you have any question, let’s discuss in the comment.