# 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[0]]*len_arr left_max = arr[0] 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[0]) == test[1]): 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.