main.py

class HistogramProblem(object):

    def __init__(self, arr):
        self.arr = arr


    def water_in_range(self, left, right):
        count = 0
        minimum = min(self.arr[left], self.arr[right])
        for i in range(left+1, right+1):
            tmp = minimum - self.arr[i]
            if tmp > 0:
                count += tmp
        return count


    def solve(self):
        left = 0
        right = len(self.arr) - 1
        water_count = 0

        ptr = left + 1
        while ptr <= right:
            if self.arr[ptr] >= self.arr[left]:
                water_count += self.water_in_range(left, ptr)
                left = ptr
            ptr += 1

        ptr = right - 1
        while ptr >= left:
            if self.arr[ptr] >= self.arr[right]:
                water_count += self.water_in_range(ptr, right)
                right = ptr
            ptr -= 1

        return water_count


print HistogramProblem([1, 0, 3, 0, 2, 0, 1, 0, 3]).solve() # Should be 13
print HistogramProblem([0, 1, 2, 3, 0, 3, 1]).solve() # Should be 3
print HistogramProblem([1, 0, 2, 3, 4]).solve() # Should be 1
print HistogramProblem([4, 0, 2, 3, 4]).solve() # Should be 7
print HistogramProblem([3, 0, 0, 0, 3]).solve() # Should be 9
print HistogramProblem([3, -2, 0, 0, 3]).solve() # Should be 11
print HistogramProblem([3, 0, 4, 0, 3]).solve() # Should be 6