3698. Split Array With Minimum Difference

MediumArrayPrefix Sum

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

Your task is to split the array into exactly two non-empty subarrays, left and right, such that:

left is the first part of the array and must be strictly increasing (every element is greater than the one before it).
right is the remaining part of the array and must be strictly decreasing (every element is smaller than the one before it).

In other words, you pick a split point: everything before it forms left, and everything from that point onward forms right. Both parts must contain at least one element, and together they must cover the entire array.

You need to return the minimum possible absolute difference between the sum of left and the sum of right, i.e., minimize |sum(left) - sum(right)| over all valid split points.

If there is no way to split the array so that both conditions hold, return -1.

For example, if nums = [1, 3, 2], splitting it as left = [1, 3] (strictly increasing) and right = [2] (strictly decreasing) is valid, and the difference is |4 - 2| = 2. Another valid split is left = [1] and right = [3, 2], giving |1 - 5| = 4. The answer would be the smaller value, 2.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Prefix Sums?

This problem maps to Prefix Sums through a short path in the full flowchart.

Precomputing prefix sums plus prefix/suffix monotonicity arrays lets each split point be checked in O(1) time.

Open in Flowchart

Intuition

The key observation is that a split is fully determined by a single index: if we cut the array after position i, then left = nums[0..i] and right = nums[i+1..n-1]. So there are only n - 1 possible splits to consider.

For each candidate split point, we need to answer two questions quickly:

Is nums[0..i] strictly increasing?
Is nums[i+1..n-1] strictly decreasing?

Checking these from scratch for every split point would cost O(n) per check, leading to O(n^2) overall. But notice that both properties have a nice prefix/suffix structure:

If a prefix [0..i] is strictly increasing, then every shorter prefix is too. Conversely, once the increasing property breaks at some position, it stays broken for all longer prefixes.
Similarly, the strictly decreasing property of suffixes can only break once as we extend the suffix to the left.

This means we can precompute the answers: an array f where f[i] tells whether the prefix ending at i is strictly increasing (built left to right), and an array g where g[i] tells whether the suffix starting at i is strictly decreasing (built right to left). Each takes a single linear pass.

The remaining piece is computing the sums of left and right efficiently. A prefix sum array s handles this: the sum of left is s[i], and the sum of right is the total minus that, s[n-1] - s[i].

Putting it together, we simply scan every split point i, and whenever f[i] and g[i+1] are both true, the split is valid and we update the answer with |s[i] - (s[n-1] - s[i])|. If no split point is ever valid, we return -1. Everything runs in O(n) time.

Pattern Learn more about Prefix Sum patterns.

Solution Approach

s = list(accumulate(nums))


Here `s[i]` stores the sum of `nums[0..i]`. This lets us get the sum of any `left` part in `O(1)`: the sum of `left = nums[0..i]` is simply `s[i]`, and the sum of `right = nums[i+1..n-1]` is `s[n-1] - s[i]`.

**Step 2: Build the prefix monotonicity array `f`**

```python
f = [True] * n
for i in range(1, n):
    f[i] = f[i - 1]
    if nums[i] <= nums[i - 1]:
        f[i] = False

f[i] indicates whether nums[0..i] is strictly increasing. A prefix of length 1 is trivially increasing, so f[0] = True. For each subsequent i, the prefix [0..i] is strictly increasing only if the shorter prefix [0..i-1] was already increasing and the new element extends it properly, i.e., nums[i] > nums[i - 1]. The recurrence inherits f[i - 1] and invalidates it when nums[i] <= nums[i - 1].

Step 3: Build the suffix monotonicity array g

g = [True] * n
for i in range(n - 2, -1, -1):
    g[i] = g[i + 1]
    if nums[i] <= nums[i + 1]:
        g[i] = False

Symmetrically, g[i] indicates whether nums[i..n-1] is strictly decreasing. We scan from right to left: g[n - 1] = True since a single element is trivially decreasing, and g[i] holds only when g[i + 1] holds and nums[i] > nums[i + 1].

Step 4: Enumerate every split point

ans = inf
for i in range(n - 1):
    if f[i] and g[i + 1]:
        s1 = s[i]
        s2 = s[n - 1] - s[i]
        ans = min(ans, abs(s1 - s2))
return ans if ans < inf else -1

Example Walkthrough

Let's trace the algorithm with nums = [1, 4, 6, 3, 1] (so n = 5).

Step 1: Prefix sums s

Running accumulate gives:

nums = [1, 4,  6,  3,  1]
s    = [1, 5, 11, 14, 15]

The total sum is s[4] = 15.

Step 2: Prefix monotonicity array f (is nums[0..i] strictly increasing?)

f[0] = True (single element).
f[1]: 4 > 1 and f[0] holds → True.
f[2]: 6 > 4 and f[1] holds → True.
f[3]: 3 <= 6 breaks the chain → False.
f[4]: inherits f[3] → False (once broken, always broken).

f = [True, True, True, False, False]

Step 3: Suffix monotonicity array g (is nums[i..n-1] strictly decreasing?), built right to left:

g[4] = True (single element).
g[3]: 3 > 1 and g[4] holds → True.
g[2]: 6 > 3 and g[3] holds → True.
g[1]: 4 <= 6 breaks the chain → False.
g[0]: inherits g[1] → False.

g = [False, False, True, True, True]

Step 4: Enumerate split points i = 0 .. 3 (the split puts nums[0..i] in left and nums[i+1..4] in right):

`i`	`left` / `right`	`f[i]`	`g[i+1]`	Valid?	`s1 = s[i]`	`s2 = 15 - s[i]`	`\|s1 - s2\|`
0	`[1]` / `[4, 6, 3, 1]`	True	False	No	—	—	—
1	`[1, 4]` / `[6, 3, 1]`	True	True	Yes	5	10	5
2	`[1, 4, 6]` / `[3, 1]`	True	True	Yes	11	4	7
3	`[1, 4, 6, 3]` / `[1]`	False	True	No	—	—	—

Split i = 0 fails because [4, 6, 3, 1] is not strictly decreasing (4 <= 6).
Split i = 3 fails because [1, 4, 6, 3] is not strictly increasing (3 <= 6).
Splits i = 1 and i = 2 are both valid, yielding differences 5 and 7.

The minimum over all valid splits is min(5, 7) = 5, so the algorithm returns 5.

Note how each step is O(1) thanks to the precomputed arrays: f and g answer the validity questions instantly, and s provides both subarray sums without re-summing. Had no row in the table been valid (e.g., for nums = [2, 5, 1, 3], where every split fails), ans would remain at infinity and the function would return -1.

Solution Implementation

1from typing import List
2from itertools import accumulate
3from math import inf
4
5
6class Solution:
7    def splitArray(self, nums: List[int]) -> int:
8        # Prefix sums of the array: prefix_sum[i] = nums[0] + ... + nums[i]
9        prefix_sum = list(accumulate(nums))
10        n = len(nums)
11
12        # is_increasing[i] is True if nums[0..i] is strictly increasing
13        is_increasing = [True] * n
14        for i in range(1, n):
15            is_increasing[i] = is_increasing[i - 1]
16            if nums[i] <= nums[i - 1]:
17                is_increasing[i] = False
18
19        # is_decreasing[i] is True if nums[i..n-1] is strictly decreasing
20        is_decreasing = [True] * n
21        for i in range(n - 2, -1, -1):
22            is_decreasing[i] = is_decreasing[i + 1]
23            if nums[i] <= nums[i + 1]:
24                is_decreasing[i] = False
25
26        ans = inf
27        # Try every split point: left part is nums[0..i], right part is nums[i+1..n-1]
28        for i in range(n - 1):
29            # A split is valid only when the left part is strictly increasing
30            # and the right part is strictly decreasing
31            if is_increasing[i] and is_decreasing[i + 1]:
32                left_sum = prefix_sum[i]
33                right_sum = prefix_sum[n - 1] - prefix_sum[i]
34                # Minimize the absolute difference between the two parts
35                ans = min(ans, abs(left_sum - right_sum))
36
37        # Return -1 if no valid split exists
38        return ans if ans < inf else -1
39

1class Solution {
2    /**
3     * Splits the array into two non-empty contiguous parts such that:
4     *   - the left part is strictly increasing, and
5     *   - the right part is strictly decreasing.
6     * Among all valid splits, returns the minimum absolute difference
7     * between the sums of the two parts. Returns -1 if no valid split exists.
8     */
9    public long splitArray(int[] nums) {
10        int n = nums.length;
11
12        // prefixSum[i] = sum of nums[0..i]
13        long[] prefixSum = new long[n];
14        prefixSum[0] = nums[0];
15
16        // increasing[i] = true if nums[0..i] is strictly increasing
17        boolean[] increasing = new boolean[n];
18        Arrays.fill(increasing, true);
19
20        // decreasing[i] = true if nums[i..n-1] is strictly decreasing
21        boolean[] decreasing = new boolean[n];
22        Arrays.fill(decreasing, true);
23
24        // Build prefix sums and the strictly-increasing flags from left to right
25        for (int i = 1; i < n; ++i) {
26            prefixSum[i] = prefixSum[i - 1] + nums[i];
27            increasing[i] = increasing[i - 1];
28            // The prefix breaks the strictly increasing property here
29            if (nums[i] <= nums[i - 1]) {
30                increasing[i] = false;
31            }
32        }
33
34        // Build the strictly-decreasing flags from right to left
35        for (int i = n - 2; i >= 0; --i) {
36            decreasing[i] = decreasing[i + 1];
37            // The suffix breaks the strictly decreasing property here
38            if (nums[i] <= nums[i + 1]) {
39                decreasing[i] = false;
40            }
41        }
42
43        final long INF = Long.MAX_VALUE;
44        long ans = INF;
45
46        // Try every split point: left part is nums[0..i], right part is nums[i+1..n-1]
47        for (int i = 0; i < n - 1; ++i) {
48            if (increasing[i] && decreasing[i + 1]) {
49                long leftSum = prefixSum[i];
50                long rightSum = prefixSum[n - 1] - prefixSum[i];
51                ans = Math.min(ans, Math.abs(leftSum - rightSum));
52            }
53        }
54
55        // If no valid split was found, return -1
56        return ans < INF ? ans : -1;
57    }
58}
59

1class Solution {
2public:
3    long long splitArray(vector<int>& nums) {
4        int n = nums.size();
5
6        // prefixSum[i] stores the sum of nums[0..i]
7        vector<long long> prefixSum(n);
8        prefixSum[0] = nums[0];
9
10        // isPrefixIncreasing[i] is true if nums[0..i] is strictly increasing
11        // isSuffixDecreasing[i] is true if nums[i..n-1] is strictly decreasing
12        vector<bool> isPrefixIncreasing(n, true), isSuffixDecreasing(n, true);
13
14        // Build prefix sums and check strictly increasing property from the left
15        for (int i = 1; i < n; ++i) {
16            prefixSum[i] = prefixSum[i - 1] + nums[i];
17            isPrefixIncreasing[i] = isPrefixIncreasing[i - 1];
18            if (nums[i] <= nums[i - 1]) {
19                isPrefixIncreasing[i] = false;
20            }
21        }
22
23        // Check strictly decreasing property from the right
24        for (int i = n - 2; i >= 0; --i) {
25            isSuffixDecreasing[i] = isSuffixDecreasing[i + 1];
26            if (nums[i] <= nums[i + 1]) {
27                isSuffixDecreasing[i] = false;
28            }
29        }
30
31        const long long INF = LLONG_MAX;
32        long long minDifference = INF;
33
34        // Try every split point: left part = nums[0..i], right part = nums[i+1..n-1]
35        for (int i = 0; i < n - 1; ++i) {
36            // A valid split requires the left part to be strictly increasing
37            // and the right part to be strictly decreasing
38            if (isPrefixIncreasing[i] && isSuffixDecreasing[i + 1]) {
39                long long leftSum = prefixSum[i];
40                long long rightSum = prefixSum[n - 1] - prefixSum[i];
41                minDifference = min(minDifference, llabs(leftSum - rightSum));
42            }
43        }
44
45        // Return -1 if no valid split exists
46        return minDifference < INF ? minDifference : -1;
47    }
48};
49

1/**
2 * Splits the array into a strictly increasing prefix and a strictly
3 * decreasing suffix, then returns the minimum absolute difference
4 * between the sums of the two parts. Returns -1 if no valid split exists.
5 *
6 * @param nums - The input array of numbers
7 * @returns The minimum absolute difference between the two parts, or -1
8 */
9function splitArray(nums: number[]): number {
10    const length: number = nums.length;
11
12    // prefixSum[i] stores the sum of nums[0..i]
13    const prefixSum: number[] = Array(length);
14
15    // isIncreasing[i] indicates whether nums[0..i] is strictly increasing
16    const isIncreasing: boolean[] = Array(length).fill(true);
17
18    // isDecreasing[i] indicates whether nums[i..length-1] is strictly decreasing
19    const isDecreasing: boolean[] = Array(length).fill(true);
20
21    // Build the prefix sums and the strictly increasing flags from left to right
22    prefixSum[0] = nums[0];
23    for (let i = 1; i < length; ++i) {
24        prefixSum[i] = prefixSum[i - 1] + nums[i];
25        isIncreasing[i] = isIncreasing[i - 1];
26
27        // The prefix is no longer strictly increasing if the current
28        // element does not exceed the previous one
29        if (nums[i] <= nums[i - 1]) {
30            isIncreasing[i] = false;
31        }
32    }
33
34    // Build the strictly decreasing flags from right to left
35    for (let i = length - 2; i >= 0; --i) {
36        isDecreasing[i] = isDecreasing[i + 1];
37
38        // The suffix is no longer strictly decreasing if the current
39        // element does not exceed the next one
40        if (nums[i] <= nums[i + 1]) {
41            isDecreasing[i] = false;
42        }
43    }
44
45    const INFINITY: number = Number.MAX_SAFE_INTEGER;
46    let answer: number = INFINITY;
47
48    // Try every split point: the first part is nums[0..i],
49    // the second part is nums[i+1..length-1]
50    for (let i = 0; i < length - 1; ++i) {
51        // A valid split requires an increasing prefix and a decreasing suffix
52        if (isIncreasing[i] && isDecreasing[i + 1]) {
53            const firstSum: number = prefixSum[i];
54            const secondSum: number = prefixSum[length - 1] - prefixSum[i];
55            answer = Math.min(answer, Math.abs(firstSum - secondSum));
56        }
57    }
58
59    // Return -1 when no valid split point was found
60    return answer < INFINITY ? answer : -1;
61}
62

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The analysis breaks down as follows:
- Building the prefix sum array s via accumulate(nums) takes O(n) time.
- Computing the array f (which marks whether the prefix nums[0..i] is strictly increasing) requires a single forward pass, taking O(n) time.
- Computing the array g (which marks whether the suffix nums[i..n-1] is strictly decreasing) requires a single backward pass, taking O(n) time.
- The final loop enumerates every possible split point i from 0 to n - 2, performing only O(1) work per iteration (checking f[i] and g[i + 1] and updating ans), contributing another O(n).
- Since all four phases run sequentially, the total time is O(n) + O(n) + O(n) + O(n) = O(n).
Space Complexity: O(n), where n is the length of the array nums. The extra space comes from:
- The prefix sum array s of size n.
- The boolean array f of size n.
- The boolean array g of size n.
- All remaining variables (ans, s1, s2, loop indices) use only O(1) space, so the overall space complexity is dominated by the three auxiliary arrays, giving O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing "strictly increasing" with "non-decreasing" (mishandling equal elements)

The most frequent mistake is writing the monotonicity check with the wrong comparison operator. Since both parts must be strictly monotonic, equal adjacent elements break the property. A buggy version looks like this:

# WRONG: allows equal adjacent values to pass as "increasing"
for i in range(1, n):
    is_increasing[i] = is_increasing[i - 1]
    if nums[i] < nums[i - 1]:        # should be <=
        is_increasing[i] = False

With nums = [2, 2, 1], this incorrectly marks the prefix [2, 2] as strictly increasing, so the split left = [2, 2], right = [1] is accepted and the code returns 3 instead of the correct answer 1 (from left = [2], right = [2, 1]).

Fix: Invalidate the flag on nums[i] <= nums[i - 1] for the prefix array and on nums[i] <= nums[i + 1] for the suffix array, exactly as the reference solution does. The same reasoning applies to the decreasing side — equality must fail there too.

2. Allowing an empty `left` or `right` part

Another easy mistake is iterating the split point over the wrong range:

# WRONG: i = n - 1 makes the right part empty
for i in range(n):
    ...

When i = n - 1, right = nums[n..n-1] is empty, and since a single-element check trivially passes most guard logic, a fully increasing array like [1, 2, 3] would wrongly return |6 - 0| = 6 instead of 0 (from left = [1, 2], right = [3]... which gives 0). Both subarrays must be non-empty by definition.

Fix: Restrict the loop to range(n - 1) so the left part is nums[0..i] with i ≤ n - 2, guaranteeing the right part nums[i+1..n-1] contains at least one element. Also note this implicitly handles n == 1: the loop body never executes and the function correctly returns -1.

3. Breaking out of the loop too early — or for the wrong reason

Some implementations try to optimize by stopping the scan once a "good" split is found:

# WRONG: the first valid split is not necessarily the best one
if is_increasing[i] and is_decreasing[i + 1]:
    return abs(s1 - s2)

Multiple valid split points can exist (e.g., a "mountain" shaped array offers several), and the minimum difference may occur at any of them. In [1, 3, 2], splitting at i = 0 gives difference 4, while i = 1 gives the optimal 2.

Fix: Enumerate all split points and track the minimum with ans = min(ans, ...). If you do want an early exit, the only safe one is breaking when is_increasing[i] becomes False, since once a prefix stops being strictly increasing, every longer prefix is also invalid — but the validity of is_decreasing[i + 1] alone never justifies stopping.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls