Watch 6 video solutions for Split Array With Minimum Difference, a medium level problem involving Array, Prefix Sum. This walkthrough by Sanyam IIT Guwahati has 618 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
Split the array into exactly two subarrays, left and right, such that left is strictly increasing and right is strictly decreasing.
Return the minimum possible absolute difference between the sums of left and right. If no valid split exists, return -1.
Example 1:
Input: nums = [1,3,2]
Output: 2
Explanation:
i |
left |
right |
Validity | left sum |
right sum |
Absolute difference |
|---|---|---|---|---|---|---|
| 0 | [1] | [3, 2] | Yes | 1 | 5 | |1 - 5| = 4 |
| 1 | [1, 3] | [2] | Yes | 4 | 2 | |4 - 2| = 2 |
Thus, the minimum absolute difference is 2.
Example 2:
Input: nums = [1,2,4,3]
Output: 4
Explanation:
i |
left |
right |
Validity | left sum |
right sum |
Absolute difference |
|---|---|---|---|---|---|---|
| 0 | [1] | [2, 4, 3] | No | 1 | 9 | - |
| 1 | [1, 2] | [4, 3] | Yes | 3 | 7 | |3 - 7| = 4 |
| 2 | [1, 2, 4] | [3] | Yes | 7 | 3 | |7 - 3| = 4 |
Thus, the minimum absolute difference is 4.
Example 3:
Input: nums = [3,1,2]
Output: -1
Explanation:
No valid split exists, so the answer is -1.
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 105Problem Overview: You are given an integer array and need to split it into two parts such that the absolute difference between their sums is minimized. The goal is to evaluate valid split points efficiently instead of recomputing sums for every partition.
Approach 1: Brute Force Split Evaluation (O(n²) time, O(1) space)
Check every possible split point and recompute the sum of the left and right subarrays each time. For a split at index i, compute sum(nums[0..i]) and sum(nums[i+1..n-1]), then update the minimum absolute difference. This approach repeatedly scans the array for sums, leading to quadratic time complexity. It works for small inputs but quickly becomes inefficient for larger arrays.
Approach 2: Prefix Sum + Two Arrays to Record Monotonicity (O(n) time, O(n) space)
Compute a prefix sum array so that any subarray sum can be derived in constant time. The total sum of the array is known once the prefix array is built. For a split at index i, the left sum is prefix[i] and the right sum is total - prefix[i]. Instead of recomputing or scanning repeatedly, maintain helper arrays that store monotonic properties of prefix values from the left and right. These arrays track the best candidate sums seen so far, allowing you to evaluate differences in a single linear pass.
The monotonic tracking ensures that while iterating through possible split points, you always compare against the most favorable prefix values discovered earlier or later in the array. This avoids nested loops and reduces the complexity to O(n). The technique combines ideas from array traversal and prefix accumulation, making it both efficient and easy to implement.
Recommended for interviews: Start by describing the brute force idea to demonstrate understanding of the problem. Then move to the prefix sum optimization. Interviewers expect the O(n) solution using prefix sums because it eliminates repeated work and shows you recognize standard array optimization patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Split Evaluation | O(n²) | O(1) | Useful for understanding the problem or when the array size is very small |
| Prefix Sum + Monotonic Helper Arrays | O(n) | O(n) | Best general solution for large arrays where repeated sum calculations must be avoided |