Island Capacity

island.py

def find_capacity(sequence):
    ''' Return the capacity of a height map.

    Here the "capacity" of a height is represented by filling a height
    map with water such that it does not spill over.

    Consider a simple height map [2, 1, 0, 1, 2, 3]:
    .....#
    #...##
    ##.###

    Here the capacity is 4, counting just the pit between index 0, and
    index 4. The algorithm runs in O(n^2) time, n being the number of
    integers in the height map.

    Args:
        sequence (list of int): The height map.

    Returns:
        int: The capacity of the height map.

    Examples:
    >>> find_capacity([2, 1, 0, 1, 2, 3])
    4
    >>> find_capacity([4, 3, 2, 9, 6, 4, 2, 2, 6, 5])
    13 '''
    left = 0
    sequence_capacity = 0
    # Starting from the left moving right
    while left < len(sequence) - 1:
        capacity = 0
        # Taking an exploratory index to traverse the arry
        for right in range(left + 1, len(sequence)):
            # If we have a point that is lower than the left point, it
            # could conceivably be part of some pit, so add the
            # difference to a potential capacity.
            if sequence[right] < sequence[left]:
                capacity += sequence[left] - sequence[right]
            else:
                # Otherwise we have reached a point that could never
                # be part of a pit including the left point or any
                # between left and right, as they must all be smaller
                # than the left. So we set right = left to search
                # further.
                left = right
                # We have gone from a start, then down, then at least
                # as much up again, so we have a pit that would hold
                # water, add this to the capacity.
                sequence_capacity += capacity
                break
        else:
            # Because we did not break from the loop, every point was
            # smaller than the left (the left is the maximum), so no
            # pit includes the left, increment and move on.
            left += 1
    return sequence_capacity