equilibrum_index.py

def brute(array):
    """ Complexity : 1 + N * ( N + N ) = 1 + 2 * N * N ~= N ^ 2
    - 1 for the len(array)
    - N for the loop(array) :
        - N for the left sum(array)
        - N for the right sum(array)
    """
    indexes = []
    length = len(array)
    for i in range(0, length):
        if sum(array[:i]) == sum(array[i + 1:]):
            indexes.append(i)
    return indexes

def fast(array):
    """ Complexity : 1 + N + N = 1 + 2 * N ~= N
    - 1 for the len(array)
    - N for the sum(array)
    - N for the loop(array)
    """
    indexes = []
    length = len(array)
    left = 0
    right = sum(array)
    for i in range(0, length):  # 0 <= i < N
        right -= array[i]  # reduce to right sum, the current A element
        if left == right:  # test sum left == sum right
            indexes.append(i)  # found index
        left += array[i]  # add to left sum, the old A element (the current one in this loop!)
    return indexes