Split Array with Equal Sum — LeetCode 548 Python Solution

The problem

Given an integer array nums of length n, return true if there is a triplet (i, j, k) which satisfies the following conditions: 0 < i, i + 1 < j, j + 1 < k < n - 1 The sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) is equal. A subarray (l, r) represents a slice of the original array starting from the element indexed l to the element indexed r.

Example

Input

nums = [1,2,1,2,1,2,1]

Output

true

Explanation

i = 1, j = 3, k = 5.

Python solution

class Solution:
    def splitArray(self, nums: List[int]) -> bool:
        n = len(nums)
        s = [0] * (n + 1)
        for i, v in enumerate(nums):
            s[i + 1] = s[i] + v
        for j in range(3, n - 3):
            seen = set()
            for i in range(1, j - 1):
                if s[i] == s[j] - s[i + 1]:
                    seen.add(s[i])
            for k in range(j + 2, n - 1):
                if s[n] - s[k + 1] == s[k] - s[j + 1] and s[n] - s[k + 1] in seen:
                    return True
        return False

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 548. Split Array with Equal Sum is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems