1712. Ways to Split Array Into Three Subarrays - Solution

Q: Is Ways to Split Array Into Three Subarrays easy or hard?

LeetCode classifies this problem as Medium. The challenge comes from translating the inequality constraints into prefix sum relationships and efficiently counting the valid range of split points without using a quadratic scan.

Q: Ways to Split Array Into Three Subarrays Python/Java solution

Python and Java implementations typically build a prefix sum array, then iterate over the first split index. The optimal version maintains two pointers to track the smallest and largest valid second split positions, resulting in an O(n) time solution.

Q: How to solve Ways to Split Array Into Three Subarrays in O(n)?

Compute prefix sums so subarray sums are constant-time operations. For each first split index i, maintain two forward-moving pointers that determine the valid range of the second split where sum(left) ≤ sum(mid) ≤ sum(right). Because the pointers never move backward, the entire algorithm completes in linear time.

Q: What is the best approach for Ways to Split Array Into Three Subarrays?

Prefix Sum with Two Pointers is the optimal approach. After building the prefix sum array, fix the first split and move two pointers to maintain the valid range for the second split. Each pointer moves forward at most n times, giving O(n) time and O(n) space complexity.

Q: Is Ways to Split Array Into Three Subarrays asked at Google/Amazon/Meta?

Problems involving prefix sums, split points, and range counting are common in interviews at companies like Google, Amazon, and Meta. Variants of this problem test whether candidates can transform sum constraints into prefix relationships and optimize with two pointers or binary search.

Q: What data structure is used in Ways to Split Array Into Three Subarrays?

The main structure is a prefix sum array, which stores cumulative sums so any subarray sum can be computed in O(1). The algorithm also uses pointer indices or binary search over the prefix array to find valid split boundaries efficiently.

Q: What is the time complexity of Ways to Split Array Into Three Subarrays?

The optimal solution runs in O(n) time using prefix sums and two pointers. A commonly implemented alternative uses binary search on the prefix sum array, which runs in O(n log n) time. Both approaches require O(n) additional space for the prefix sum array.

The problem

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 10⁹+ 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 <= 10⁵
0 <= nums[i] <= 10⁴

Approach overview

Problem Overview: Given an integer array, split it into three non-empty contiguous subarrays left, mid, and right. The split is valid when sum(left) ≤ sum(mid) ≤ sum(right). The goal is to count how many index pairs (i, j) create such a split.

Approach 1: Prefix Sum and Two Pointers (O(n) time, O(n) space)

First compute a prefix sum array so any subarray sum can be calculated in O(1). Fix the first split index i, which determines the left subarray. Then move two pointers j and k to represent the valid range of the second split that forms the mid subarray. Increase j until sum(mid) ≥ sum(left), and increase k while sum(mid) ≤ sum(right). Because both pointers only move forward across the array, the total work stays linear. This technique combines array traversal with two pointers to efficiently count all valid positions.

Approach 2: Prefix Sum and Binary Search (O(n log n) time, O(n) space)

Use the prefix sum array to convert the constraints into numeric bounds. For each first split index i, the second split index j must satisfy two inequalities: prefix[j] - prefix[i] ≥ prefix[i] and prefix[j] - prefix[i] ≤ total - prefix[j]. Rearranging these conditions gives a valid range of prefix values for j. Because the prefix array is non-decreasing, you can use binary search to find the first and last valid indices. The number of valid splits for that i equals the size of this range. This approach is straightforward to implement and easier to reason about than pointer movement.

Recommended for interviews: Prefix Sum with Two Pointers is the expected optimal approach. It reduces the search space from O(n log n) to O(n) by exploiting the monotonic movement of valid split boundaries. Showing the binary search approach first demonstrates understanding of prefix sums and range constraints, but implementing the linear two-pointer solution shows stronger algorithmic optimization skills.

Approach 1: Prefix Sum and Two Pointers

In this method, we utilize a prefix sum array to speed up the calculation of subarray sums. Using two pointers, we attempt to find ranges for the middle subarray that satisfy the given constraints for each choice of the first split point.

Python

def waysToSplit(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    count = 0
    MOD = 10**9 + 7
    j = k = 2
    for i in range(1, n - 1):
        while j < n and prefix[j] - prefix[i] < prefix[i]:
            j += 1
        while k < n and prefix[k] - prefix[i] <= prefix[n] - prefix[k]:
            k += 1
        count = (count + k - j) % MOD
    return count

# Example usage
nums = [1, 2, 2, 2, 5, 0]
print(waysToSplit(nums))

Java

import java.util.*;

public class WaysToSplit {
    public int waysToSplit(int[] nums) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int count = 0, MOD = 1000000007;
        for (int i = 1, j = 2, k = 2; i < n - 1; ++i) {
            while (j < n && prefix[j] < 2 * prefix[i]) j++;
            while (k < n && prefix[k] - prefix[i] <= prefix[n] - prefix[k]) k++;
            count = (count + (k - j) % MOD) % MOD;
        }
        return count;
    }

    public static void main(String[] args) {
        WaysToSplit solution = new WaysToSplit();
        int[] nums = {1, 2, 2, 2, 5, 0};
        System.out.println(solution.waysToSplit(nums));
    }
}

C++

#include <vector>
#include <iostream>

int waysToSplit(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<long long> prefix(n + 1, 0);
    const int MOD = 1e9 + 7;
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    int count = 0;
    for (int i = 1, j = 2, k = 2; i < n - 1; ++i) {
        while (j < n && prefix[j] < 2 * prefix[i]) j++;
        while (k < n && prefix[k] - prefix[i] <= prefix[n] - prefix[k]) k++;
        count = (count + (k - j)) % MOD;
    }
    return count;
}

int main() {
    std::vector<int> nums = {1, 2, 2, 2, 5, 0};
    std::cout << waysToSplit(nums) << std::endl;
    return 0;
}

JavaScript

function waysToSplit(nums) {
    let n = nums.length;
    let prefix = new Array(n + 1).fill(0);
    const MOD = 1e9 + 7;
    for (let i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    let count = 0;
    let j = 2, k = 2;
    for (let i = 1; i < n - 1; ++i) {
        while (j < n && prefix[j] < 2 * prefix[i]) j++;
        while (k < n && prefix[k] - prefix[i] <= prefix[n] - prefix[k]) k++;
        count = (count + (k - j)) % MOD;
    }
    return count;
}

// Example usage
let nums = [1, 2, 2, 2, 5, 0];
console.log(waysToSplit(nums));

#include <stdio.h>
#define MOD 1000000007

int waysToSplit(int* nums, int numsSize) {
    long prefix[100001] = {0};
    for (int i = 0; i < numsSize; ++i) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    int count = 0;
    for (int i = 1, j = 2, k = 2; i < numsSize - 1; ++i) {
        while (j < numsSize && prefix[j] < 2 * prefix[i]) j++;
        while (k < numsSize && prefix[k] - prefix[i] <= prefix[numsSize] - prefix[k]) k++;
        count = (count + (k - j)) % MOD;
    }
    return count;
}

int main() {
    int nums[] = {1, 2, 2, 2, 5, 0};
    int result = waysToSplit(nums, sizeof(nums)/sizeof(nums[0]));
    printf("%d\n", result);
    return 0;
}

using System;

public class Solution {
    public int WaysToSplit(int[] nums) {
        int n = nums.Length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int count = 0, MOD = 1000000007;
        int j = 2, k = 2;
        for (int i = 1; i < n - 1; ++i) {
            while (j < n && prefix[j] - prefix[i] < prefix[i]) j++;
            while (k < n && prefix[k] - prefix[i] <= prefix[n] - prefix[k]) k++;
            count = (count + (k - j)) % MOD;
        }
        return count;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = new int[] { 1, 2, 2, 2, 5, 0 };
        Console.WriteLine(sol.WaysToSplit(nums));
    }
}

This Python code follows a similar approach using a prefix sum array complemented with two pointers to explore valid splits of the input array. Modulo operations ensure result constraints.

Complexity

Time Complexity: O(n), all operations within the loop only occur in linear relation to input size.
Space Complexity: O(n), prefix sum array requires space proportional to input size.

Try this approach in the editor

Approach 2: Prefix Sum and Binary Search

This method uses a prefix sum array to manage efficiency and applies binary search to quickly determine the bounds needed for a proper split, checking for valid middle subarrays using binary search for faster lookup of boundaries.

Python

import bisect

def waysToSplit(nums):
    MOD = 10**9 + 7
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    count = 0
    for i in range(1, n - 1):
        j = bisect.bisect_left(prefix, 2 * prefix[i], i + 1, n)
        k = bisect.bisect_right(prefix, (prefix[n] + prefix[i]) // 2, j, n)
        count = (count + k - j) % MOD
    return count

# Example Usage
nums = [1, 2, 2, 2, 5, 0]
print(waysToSplit(nums))

Java

import java.util.*;

public class WaysToSplit {
    private int lowerBound(long[] prefix, int start, int end, long target) {
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (prefix[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }

    private int upperBound(long[] prefix, int start, int end, long target) {
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (prefix[mid] <= target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }

    public int waysToSplit(int[] nums) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int count = 0;
        int MOD = 1000000007;
        for (int i = 1; i < n - 1; i++) {
            int j = lowerBound(prefix, i + 1, n, 2 * prefix[i]);
            int k = upperBound(prefix, j, n, (prefix[n] + prefix[i]) / 2);
            count = (count + k - j) % MOD;
        }
        return count;
    }

    public static void main(String[] args) {
        WaysToSplit solution = new WaysToSplit();
        int[] nums = {1, 2, 2, 2, 5, 0};
        System.out.println(solution.waysToSplit(nums));
    }
}

C++

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int waysToSplit(vector<int>& nums) {
    int n = nums.size();
    vector<long> prefix(n + 1, 0);
    const int MOD = 1e9 + 7;
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    int count = 0;
    for (int i = 1; i < n - 1; ++i) {
        int j = lower_bound(prefix.begin() + i + 1, prefix.begin() + n, 2 * prefix[i]) - prefix.begin();
        int k = upper_bound(prefix.begin() + j, prefix.begin() + n, prefix[i] + (prefix[n] - prefix[i]) / 2) - prefix.begin();
        count = (count + k - j) % MOD;
    }
    return count;
}

int main() {
    vector<int> nums = {1, 2, 2, 2, 5, 0};
    cout << waysToSplit(nums) << endl;
    return 0;
}

JavaScript

function lowerBound(prefix, start, end, target) {
    while (start < end) {
        let mid = Math.floor((start + end) / 2);
        if (prefix[mid] < target) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return start;
}

function upperBound(prefix, start, end, target) {
    while (start < end) {
        let mid = Math.floor((start + end) / 2);
        if (prefix[mid] <= target) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return start;
}

function waysToSplit(nums) {
    let n = nums.length;
    let prefix = new Array(n + 1).fill(0);
    const MOD = 1e9 + 7;
    for (let i = 0; i < n; ++i) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    let count = 0;
    for (let i = 1; i < n - 1; ++i) {
        let j = lowerBound(prefix, i + 1, n, 2 * prefix[i]);
        let k = upperBound(prefix, j, n, (prefix[n] + prefix[i]) / 2);
        count = (count + (k - j)) % MOD;
    }
    return count;
}

// Example usage
let nums = [1, 2, 2, 2, 5, 0];
console.log(waysToSplit(nums));

#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000007

int lower_bound(long* prefix, int start, int end, long target) {
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (prefix[mid] < target) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return start;
}

int upper_bound(long* prefix, int start, int end, long target) {
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (prefix[mid] <= target) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return start;
}

int waysToSplit(int* nums, int numsSize) {
    long prefix[numsSize + 1];
    prefix[0] = 0;
    for (int i = 0; i < numsSize; ++i) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    int count = 0;
    for (int i = 1; i < numsSize - 1; ++i) {
        int j = lower_bound(prefix, i + 1, numsSize, 2 * prefix[i]);
        int k = upper_bound(prefix, j, numsSize, (prefix[numsSize] + prefix[i]) / 2);
        count = (count + k - j) % MOD;
    }
    return count;
}

int main() {
    int nums[] = {1, 2, 2, 2, 5, 0};
    int result = waysToSplit(nums, sizeof(nums)/sizeof(nums[0]));
    printf("%d\n", result);
    return 0;
}

using System;

public class Solution {
    private int LowerBound(long[] prefix, int start, int end, long target) {
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (prefix[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }

    private int UpperBound(long[] prefix, int start, int end, long target) {
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (prefix[mid] <= target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }

    public int WaysToSplit(int[] nums) {
        int n = nums.Length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int count = 0;
        int MOD = 1000000007;
        for (int i = 1; i < n - 1; i++) {
            int j = LowerBound(prefix, i + 1, n, 2 * prefix[i]);
            int k = UpperBound(prefix, j, n, (prefix[n] + prefix[i]) / 2);
            count = (count + k - j) % MOD;
        }
        return count;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = new int[] { 1, 2, 2, 2, 5, 0 };
        Console.WriteLine(sol.WaysToSplit(nums));
    }
}

Within Python, the bisect module facilitates rapid distinction of lower and upper bounds for subarrays, reducing time to find valid splits within the prefix sum array. This approach handles searching with balanced efficiency.

Complexity

Time Complexity: O(n log n), involving binary searches in both bisect_left and bisect_right functions.
Space Complexity: O(n), primarily spent on the prefix sum.

Try this approach in the editor

Approach 3: Prefix Sum + Binary Search

First, we preprocess the prefix sum array s of the array nums, where s[i] represents the sum of the first i+1 elements of the array nums.

Since all elements of the array nums are non-negative integers, the prefix sum array s is a monotonically increasing array.

We enumerate the index i that the left subarray can reach in the range [0,..n-2), and then use the monotonically increasing characteristic of the prefix sum array to find the reasonable range of the mid subarray split by binary search, denoted as [j, k), and accumulate the number of schemes k-j.

In the binary search details, the subarray split must satisfy s[j] geq s[i] and s[n - 1] - s[k] geq s[k] - s[i]. That is, s[j] geq s[i] and s[k] leq \frac{s[n - 1] + s[i]}{2}.

Finally, return the number of schemes modulo 10^9+7.

The time complexity is O(n times log n), where n is the length of the array nums.

func waysToSplit(nums []int) (ans int) {
	const mod int = 1e9 + 7
	n := len(nums)
	s := make([]int, n)
	s[0] = nums[0]
	for i := 1; i < n; i++ {
		s[i] = s[i-1] + nums[i]
	}
	for i := 0; i < n-2; i++ {
		j := sort.Search(n-1, func(h int) bool { return h > i && s[h] >= (s[i]<<1) })
		k := sort.Search(n-1, func(h int) bool { return h >= j && s[h] > (s[n-1]+s[i])>>1 })
		ans = (ans + k - j) % mod
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Prefix Sum and Two Pointers	Time Complexity: O(n), all operations within the loop only occur in linear relation to input size. Space Complexity: O(n), prefix sum array requires space proportional to input size.
Prefix Sum and Binary Search	Time Complexity: O(n log n), involving binary searches in both `bisect_left` and `bisect_right` functions. Space Complexity: O(n), primarily spent on the prefix sum.
Prefix Sum + Binary Search	–

Complexity analysis

Approach	Time	Space	When to Use
Prefix Sum + Two Pointers	O(n)	O(n)	Best overall approach. Linear scan with monotonic pointers for maximum efficiency.
Prefix Sum + Binary Search	O(n log n)	O(n)	Simpler reasoning. Useful when pointer window logic feels tricky.

Frequently asked questions

Is Ways to Split Array Into Three Subarrays easy or hard?

LeetCode classifies this problem as Medium. The challenge comes from translating the inequality constraints into prefix sum relationships and efficiently counting the valid range of split points without using a quadratic scan.

Ways to Split Array Into Three Subarrays Python/Java solution

Python and Java implementations typically build a prefix sum array, then iterate over the first split index. The optimal version maintains two pointers to track the smallest and largest valid second split positions, resulting in an O(n) time solution.

How to solve Ways to Split Array Into Three Subarrays in O(n)?

Compute prefix sums so subarray sums are constant-time operations. For each first split index i, maintain two forward-moving pointers that determine the valid range of the second split where sum(left) ≤ sum(mid) ≤ sum(right). Because the pointers never move backward, the entire algorithm completes in linear time.

What is the best approach for Ways to Split Array Into Three Subarrays?

Prefix Sum with Two Pointers is the optimal approach. After building the prefix sum array, fix the first split and move two pointers to maintain the valid range for the second split. Each pointer moves forward at most n times, giving O(n) time and O(n) space complexity.

Is Ways to Split Array Into Three Subarrays asked at Google/Amazon/Meta?

Problems involving prefix sums, split points, and range counting are common in interviews at companies like Google, Amazon, and Meta. Variants of this problem test whether candidates can transform sum constraints into prefix relationships and optimize with two pointers or binary search.

What data structure is used in Ways to Split Array Into Three Subarrays?

The main structure is a prefix sum array, which stores cumulative sums so any subarray sum can be computed in O(1). The algorithm also uses pointer indices or binary search over the prefix array to find valid split boundaries efficiently.

What is the time complexity of Ways to Split Array Into Three Subarrays?

The optimal solution runs in O(n) time using prefix sums and two pointers. A commonly implemented alternative uses binary search on the prefix sum array, which runs in O(n log n) time. Both approaches require O(n) additional space for the prefix sum array.

Ways to Split Array Into Three Subarrays solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum and Two Pointers

Approach 2: Prefix Sum and Binary Search

Approach 3: Prefix Sum + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Ways to Split Array Into Three Subarrays solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum and Two Pointers

Approach 2: Prefix Sum and Binary Search

Approach 3: Prefix Sum + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems