Problem statement

https://leetcode.com/problems/split-array-with-equal-sum/

Solution

Brute-force solutions are O(n^4) or O(n^3) if we compute cumulative sums. We can do better: let as fix number j, then we need to split first part and second. Let us iterate over first part: before j and keep in set numbers, for which we can split this part, such that both new parts equal to this number. For example if we have $[1,2,3,4,-4,10]$ we can split them as $[1,2,3,4];[10]$ or $[1,2,3];[-4,10]$, so we put $10$ and $6$ into set. We do the same for the part after $j$ and then check if these two sets have intersection.

Complexity

Time complexity will be O(n^2), space complexity is O(n).

Code

class Solution:
    def splitArray(self, nums):
        def split(arr):
            vals = set()
            if not arr: return vals
            acc = [0] + list(accumulate(arr))
            lft, rgh = 0, acc[-1] - acc[1]
            for i in range(1, len(arr) - 1):
                lft += arr[i-1]
                rgh -= arr[i]
                if lft == rgh: vals.add(lft)
            return vals

        acc = [0] + list(accumulate(nums))
        for i in range(len(nums)):
            lft, rgh = nums[:i], nums[i+1:]
            if split(lft) & split(rgh): return True

        return False