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

Ways to Split Array Into Three Subarrays

Number: 1831

Difficulty: Medium

Paid? No

Companies: Google, Robinhood

Problem Description

Given a non-negative integer array nums, count the number of ways to split nums into three contiguous non-empty subarrays – named left, mid, and right – such that the sum of left is less than or equal to the sum of mid, and the sum of mid is less than or equal to the sum of right. Return the count modulo 10^9+7.

Key Insights

  • A prefix sum array is used to quickly compute sums for any subarray.
  • Transform the conditions into constraints on prefix sums:
    • For a chosen left ending index i, ensure that the mid subarray starting index j satisfies: prefix[j] >= 2 * prefix[i].
    • Also, ensure that mid subarray sum condition holds: prefix[j] <= (total + prefix[i]) / 2.
  • Utilize binary search (or two pointers) to efficiently determine the valid range of mid indices for each i.
  • Each valid range contributes to the count of good splits.

Space and Time Complexity

Time Complexity: O(n log n) using binary search (O(n) with two pointers) Space Complexity: O(n) for the prefix sum array

Solution

We first calculate a prefix sum array from nums. For each possible end index i of the left subarray, we need to determine the range of indices j (which will mark the end of the mid subarray) that satisfy the constraints:

  1. The sum of left (prefix[i]) is <= the sum of mid (prefix[j] - prefix[i]) which gives prefix[j] >= 2*prefix[i].
  2. The sum of mid is <= the sum of right (total - prefix[j]) leading to prefix[j] <= (total + prefix[i]) / 2. For each i, binary search (or two pointers) is used to locate the lower bound of j and the upper bound of j. The contribution to the overall count is the number of valid j indices in that range. Finally, the answer is returned modulo 10^9+7.

Code Solutions

# Python solution using prefix sum and binary search
from bisect import bisect_left, bisect_right

def waysToSplit(nums):
    MOD = 10**9 + 7
    n = len(nums)
    # Compute prefix sums
    prefix = [0] * n
    prefix[0] = nums[0]
    for i in range(1, n):
        prefix[i] = prefix[i - 1] + nums[i]
    total = prefix[-1]
    count = 0
    
    # Iterate over possible splits for the left subarray
    for i in range(n - 2):
        leftSum = prefix[i]
        # Find the smallest index j where prefix[j] >= 2 * leftSum
        lo = bisect_left(prefix, 2 * leftSum, i + 1, n - 1)
        # Find the first index j where prefix[j] > (total + leftSum) // 2
        hi = bisect_right(prefix, (total + leftSum) // 2, i + 1, n - 1)
        if lo < hi:
            count = (count + hi - lo) % MOD
    return count

# Example usage:
print(waysToSplit([1,1,1]))
← Back to All Questions