Ways to Split Array Into Three Subarrays - Solution & Explanation

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.

MediumArray Two Pointers Binary Search Prefix Sum21 min readAsked at: Robinhood, Google, Tekion

Practice this problem

Problem Statement

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.

We create a prefix sum array where prefix[i] stores the sum of numbers from start to i-1. We loop over possible positions for the first cut and then use two pointers.

Pointer j: Finds the first valid position for the second cut.
Pointer k: Ensures the second cut remains valid for right subarray constraints.

The loop updates the count for valid splits by calculating k - j, and then we apply the modulo operation.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the size of the array. Each step in the algorithm processes elements in linear time.
Space Complexity: O(n), for storing the prefix sum array.

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.

This C solution combines prefix sums with binary searches via custom lower and upper bound functions to swiftly determine the range of indices that work for a valid middle subarray, both optimized with binary search.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n log n), due to binary searches.
Space Complexity: O(n), for prefix sums.

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.

Code

Python Java C++Go JavaScript

Python

Java

C++

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Prefix Sum and Two Pointers	Time Complexity: O(n), where n is the size of the array. Each step in the algorithm processes elements in linear time. Space Complexity: O(n), for storing the prefix sum array.
Prefix Sum and Binary Search	Time Complexity: O(n log n), due to binary searches. Space Complexity: O(n), for prefix sums.
Prefix Sum + Binary Search	—

Detailed 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.

Video Solution

LeetCode 1712. Ways to Split Array Into Three Subarrays | Visualization | Python • AH Tech • 7,537 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Ways to Split Array Into Three Subarrays with our built-in code editor and test cases.

Practice on FleetCode

Number of Ways to Divide a Long Corridor

Number of Ways to Split Array

Problem Info

DifficultyMedium

Acceptance34.2%

Approaches3

Reading time21 min

Asked at

Robinhood Google Tekion

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Prefix Sum and Two Pointers

Code

Complexity

Approach 2: Prefix Sum and Binary Search

Code

Complexity

Approach 3: Prefix Sum + Binary Search

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents