Scale Engineer

Ways to Split Array Into Three Subarrays

Med
#1569Time: O(n^2) due to the nested loops iterating through all possible pairs of split points `(i, j)`. The prefix sum calculation takes O(n).Space: O(n) to store the prefix sum array.2 companies
Patterns
Two PointersPrefix Sum
Algorithms
Binary Search
Data structures
Array
Companies
TekionRobinhood

Prompt

A split of an integer array is good if:

  • The array is split into three non-empty contiguous subarrays - named left, mid, right respectively from left to right.
  • The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].

Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

 

Constraints:

  • 3 <= nums.length <= 105
  • 0 <= nums[i] <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through all possible ways to split the array into three non-empty parts. A split is defined by two indices, i and j, where the first subarray ends at i-1 and the second ends at j-1. We can use nested loops to check every valid pair of (i, j). To make the sum calculation efficient, we first compute a prefix sum array. This allows us to find the sum of any subarray in constant time. For each pair of (i, j), we calculate the sums of the left, mid, and right subarrays and check if they satisfy the required conditions.

Algorithm

  • Pre-calculate a prefix sum array, prefix, where prefix[k] stores the sum of the first k elements of nums.
  • Initialize a counter count to 0.
  • Use two nested loops to iterate through all possible split points i and j.
    • The outer loop for the first split point i runs from 1 to n-2.
    • The inner loop for the second split point j runs from i+1 to n-1.
  • Inside the inner loop, calculate the sums of the three subarrays (left, mid, right) in O(1) time using the prefix sum array:
    • sum_left = prefix[i]
    • sum_mid = prefix[j] - prefix[i]
    • sum_right = prefix[n] - prefix[j]
  • Check if the conditions sum_left <= sum_mid and sum_mid <= sum_right are satisfied.
  • If they are, increment the count.
  • After the loops complete, return count modulo 10^9 + 7.

Walkthrough

The core idea is to exhaustively check every possible pair of split points. Let the array nums have length n. A split is determined by two indices, i and j, which represent the end of the left subarray and the end of the mid subarray, respectively. The left part is nums[0...i-1], mid is nums[i...j-1], and right is nums[j...n-1]. To ensure all three subarrays are non-empty, i must be at least 1, and j must be at least i+1. Also, j must be less than n to leave a non-empty right part. This gives us the loop bounds: i from 1 to n-2 and j from i+1 to n-1.

To avoid re-calculating sums repeatedly, which would lead to an O(n^3) solution, we pre-compute a prefix sum array. Let prefix[k] be the sum of elements from nums[0] to nums[k-1]. Then, sum(left) = prefix[i], sum(mid) = prefix[j] - prefix[i], and sum(right) = prefix[n] - prefix[j]. With these O(1) sum calculations, the overall complexity is dominated by the nested loops, resulting in O(n^2).

class Solution {    public int waysToSplit(int[] nums) {        int n = nums.length;        int MOD = 1_000_000_007;        int[] prefix = new int[n + 1];        for (int i = 0; i < n; i++) {            prefix[i + 1] = prefix[i] + nums[i];        }         long count = 0;        // i is the first split point (exclusive), left part is [0, i-1]        for (int i = 1; i < n; i++) {            // j is the second split point (exclusive), mid part is [i, j-1]            for (int j = i + 1; j < n; j++) {                int sum_left = prefix[i];                int sum_mid = prefix[j] - prefix[i];                int sum_right = prefix[n] - prefix[j];                 if (sum_left <= sum_mid && sum_mid <= sum_right) {                    count++;                }            }        }         return (int) (count % MOD);    }}

Complexity

Time

O(n^2) due to the nested loops iterating through all possible pairs of split points `(i, j)`. The prefix sum calculation takes O(n).

Space

O(n) to store the prefix sum array.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for smaller input sizes.

Cons

  • The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {private  static final int MOD = (int)1 e9 + 7;public  int waysToSplit(int[] nums) {    int n = nums.length;    int[] s = new int[n];    s[0] = nums[0];    for (int i = 1; i < n; ++i) {      s[i] = s[i - 1] + nums[i];    }    int ans = 0;    for (int i = 0; i < n - 2; ++i) {      int j = search(s, s[i] << 1, i + 1, n - 1);      int k = search(s, ((s[n - 1] + s[i]) >> 1) + 1, j, n - 1);      ans = (ans + k - j) % MOD;    }    return ans;  }private  int search(int[] s, int x, int left, int right) {    while (left < right) {      int mid = (left + right) >> 1;      if (s[mid] >= x) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem