Ways to Split Array Into Three Subarrays

Ways to Split Array Into Three Subarrays

What is this problem about?

The "Ways to Split Array Into Three Subarrays" problem asks you to find the number of ways to divide a non-negative integer array into three non-empty, contiguous subarrays—left, mid, and right. The split must satisfy a specific condition: the sum of the elements in the left subarray must be less than or equal to the sum of the mid subarray, and the sum of the mid subarray must be less than or equal to the sum of the right subarray.

Why is this asked in interviews?

This is a high-signal question for companies like Google and Robinhood because it tests a candidate's ability to optimize a search space. A naive O(N^3) or even O(N^2) solution will fail for large inputs. It requires a deep understanding of Prefix Sums and how to use either Binary Search or Two Pointers to find the valid boundaries for the "mid" subarray in O(N) or O(N log N) time.

Algorithmic pattern used

The problem primarily uses Prefix Sums to allow constant-time subarray sum calculations. Once the prefix sums are ready, for each possible end-index of the "left" subarray, you must find the range of indices where the "mid" subarray can end. This range can be found using Binary Search (to find the lower and upper bounds of the mid-sum) or a Three-Pointer approach (to track the boundaries linearly).

Example explanation

Array: [1, 2, 2, 2, 5, 0]. Prefix Sums: [1, 3, 5, 7, 12, 12]. Total Sum = 12.

1. If Left = [1] (sum 1).
2. We need Mid sum ≥ 1 and Right sum ≥ Mid sum.
3. Possible Mid subarrays:
   • [2] (sum 2). Remaining Right [2, 2, 5, 0] (sum 9). Valid.
   • [2, 2] (sum 4). Remaining Right [2, 5, 0] (sum 7). Valid.
   • [2, 2, 2] (sum 6). Remaining Right [5, 0] (sum 5). Invalid (Mid > Right). For each Left split, we count these valid Mid splits and sum them up.

Common mistakes candidates make

• Ignoring 0s: Arrays with many zeros can have multiple valid split points that result in the same sums. Candidates often miscount these.
• Off-by-one in Binary Search: Finding the exact "first valid" and "last valid" index for the mid-subarray is tricky.
• Overflow: Even if the input is small, the number of ways can exceed a standard 32-bit integer, so using modulo is essential.

Interview preparation tip

When you see a problem involving "sum of subarrays" and "partitions," immediately think of Prefix Sums. If the array is non-negative, the prefix sum array is monotonically increasing, which is a huge hint that you can use Binary Search.