We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Split Array with Equal Sum

Number: 548

Difficulty: Hard

Paid? Yes

Companies: Alibaba

Problem Description

Given an integer array nums of length n, determine if there exist indices (i, j, k) that satisfy:

  • 0 < i, i + 1 < j, j + 1 < k < n - 1.
  • The sums of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1), and (k + 1, n - 1) are all equal.

A subarray (l, r) is a slice from index l to index r of the array.

Key Insights

  • Use a prefix sum array to compute subarray sums in constant time.
  • For a fixed middle index j, iterate over possible i (for the first two segments) and k (for the last two segments).
  • Store valid sums from the left part in a set for quick lookup.
  • Validate that the sums of the segments on both sides match the candidate sum.
  • Ensure the indices follow the strict ordering imposed by the problem.

Space and Time Complexity

Time Complexity: O(n²), where n is the length of the array. Space Complexity: O(n), primarily for the prefix sum and hash set.

Solution

The approach begins by calculating a prefix sum array, so any subarray sum can be computed in O(1) time. For each possible middle index j (satisfying the given index conditions), we iterate over possible i values for the left segments and add valid equal sums to a set. Then, for the right side, we iterate over possible k and check if the sum from (j+1, k-1) matches the required condition and exists in the set. This guarantees that all four subarray segments have the same sum. Key challenges include managing index boundaries carefully to not violate any constraints.

Code Solutions

# Python solution with comments
class Solution:
    def splitArray(self, nums):
        n = len(nums)
        # There must be at least 7 elements to split into 4 parts.
        if n < 7:
            return False
        
        # Create prefix sum array: prefix_sum[i] = sum(nums[0]..nums[i])
        prefix_sum = [0] * n
        prefix_sum[0] = nums[0]
        for i in range(1, n):
            prefix_sum[i] = prefix_sum[i - 1] + nums[i]
        
        # Function to compute subarray sum from index l to r
        def get_sum(l, r):
            if l == 0:
                return prefix_sum[r]
            return prefix_sum[r] - prefix_sum[l - 1]
        
        # j is the middle cut. j must be between 3 and n-4 inclusive.
        for j in range(3, n - 3):
            found_sums = set()
            # Try every possible i for the left split (1 <= i < j-1)
            for i in range(1, j - 1):
                if get_sum(0, i - 1) == get_sum(i + 1, j - 1):
                    found_sums.add(get_sum(0, i - 1))
            
            # Try every possible k for the right split (j+2 <= k < n-1)
            for k in range(j + 2, n - 1):
                if get_sum(j + 1, k - 1) == get_sum(k + 1, n - 1):
                    if get_sum(j + 1, k - 1) in found_sums:
                        return True
        return False
← Back to All Questions