Trying to find element in an array from which the sum of elements on the left side is equal to eleme-CodePudding

def balancedSums(arr):
    n = len(arr)
    for i in range(0, n):
        lsum = sum(arr[0 : i])
        rsum = sum(arr[i   1 : n])
        if lsum == rsum:
            return "YES"
    return "NO"

I am getting all test cases but two, failing due to timeout. What are my options?

CodePudding user response：

You can do something like that:

def balancedSums(arr):
    lsum = 0
    rsum = sum(arr)
    n = len(arr)
    for i in range(0, n):
        rsum -= arr[i]
        if lsum == rsum:
            return "YES"
        lsum  = arr[i]
    return "NO"

The time-complexity of this is O(n)

CodePudding user response：

I tried to think of a vectorized way to do this with Numpy. This is the best I have come up with so far:

import numpy as np

def balancedSums(arr):
    arr = np.array(arr)
    ltr = np.cumsum(arr)
    rtl = np.cumsum(arr[::-1])[::-1]
    if np.any(ltr == rtl):
        return "YES"
    else:
        return "NO"

assert(balancedSums([1, 2, 3]) == "NO")
assert(balancedSums([3, 2, 1, 2, 3]) == "YES")
assert(balancedSums([10]) == "YES")
assert(balancedSums([1, 1]) == "NO")
assert(balancedSums([0]) == "YES")
assert(balancedSums([]) == "NO")