Calculate trapped water in a structure

Question

Supposed my input is [1, 4, 2, 5, 1, 2, 3] . Then we can create a structure like this:

...X...
.X.X...
.X.X..X
.XXX.XX
XXXXXXX
1425123

When water is poured over the top at all places and allowed to runoff, it will remain trapped at the 'O' locations:

...X...
.XOX...
.XOXOOX
.XXXOXX
XXXXXXX
1425123

we have to find a total number of trapped 'O' in a given list.

My program is able to give me the correct output but when I run it against different test cases, it gives me a memory error. Is there any way I can reduce the space complexity of this program?

def answer(heights):
    row = len(heights)
    col = max(heights)
    sum = 0
    matrix = [['X' for j in range(i)] for i in heights]
    for i in range(col):
        rainWater = []
        for j in range(row):
            try:
                rainWater.append(matrix[j][i])
            except IndexError:
                rainWater.append('0')
        sum += ''.join(rainWater).strip('0').count('0')
    return sum

print answer([1, 4, 2, 5, 1, 2, 3])

The list array will have at least 1 element and at most 9000 elements. Each element will have a value of at least 1, and at most 100000.

Inputs:
    (int list) heights = [1, 4, 2, 5, 1, 2, 3]

Output:
    (int) 5

Inputs:
    (int list) heights = [1, 2, 3, 2, 1]

Output:
    (int) 0

Answer 1

This can be solved in linear time with linear memory requirements in the following way:

def answer(heights):
    minLeft = [0] * len(heights)
    left = 0
    for idx, h in enumerate(heights):
        if left < h:
            left = h
        minLeft[idx] = left

    minRight = [0] * len(heights)
    right = 0
    for idx, h in enumerate(heights[::-1]):
        if right < h:
            right = h
        minRight[len(heights) - 1 - idx] = right

    water = 0
    for h, l, r in zip(heights, minLeft, minRight):
        water += min([l, r]) - h

    return water

The arrays minLeft and minRight contain the highest level at which water can be supported at a place in the array if there was a wall of infinite size on the right or left side respectively. Then at each index, total water that can be contained is the minimum of the water levels supported by the left and the right side - height of the floor.

---

This question deals with this problem in higher dimension (relating it to the Watershed problem in image processing): The Maximum Volume of Trapped Rain Water in 3D