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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Ways to Split Array Into Three Subarrays

Difficulty: Medium

Problem Description

Given an integer array nums, we want to find the number of ways to split the array into three non-empty contiguous subarrays such that the sum of the elements in the left subarray is less than or equal to the sum of the elements in the middle subarray, and the sum of the middle subarray is less than or equal to the sum of the right subarray. The result should be returned modulo 10^9 + 7.

Key Insights

  • The array must be split into three non-empty parts.
  • The sums of these parts must satisfy the conditions: sum(left) <= sum(mid) <= sum(right).
  • A prefix sum array can be utilized to efficiently calculate the sums of subarrays.
  • Use two pointers to determine the valid ranges for the left and middle subarrays.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a prefix sum array to calculate the cumulative sums of the elements in nums. This allows us to efficiently compute the sums of any contiguous subarray. The two-pointer technique is employed to find the valid positions for the splits. Specifically, we will iterate through possible split points for the middle subarray and keep track of valid ranges for the left and right subarrays. The counts of valid configurations are accumulated and returned.

Code Solutions

def waysToSplit(nums):
    MOD = 10**9 + 7
    n = len(nums)
    
    # Calculate prefix sums
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + nums[i]
    
    count = 0
    j = 0  # Pointer for mid start
    
    for i in range(1, n - 1):
        while j < n - 1 and prefix_sum[j + 1] - prefix_sum[i] < prefix_sum[i]:
            j += 1
        k = j
        
        while k < n - 1 and prefix_sum[n] - prefix_sum[k + 1] < prefix_sum[k + 1] - prefix_sum[i]:
            k += 1

        count += k - j + 1
    
    return count % MOD
← Back to All Questions