Split Array With Minimum Difference solution and explanation
Google
3 more videos on this problem
Split Array With Minimum Difference | LeetCode 3698 | Weekly Contest 469Sanyam IIT Guwahati · 10:11 · 644 views
3698. Split Array With Minimum Difference (Leetcode Medium)Programming Live with Larry · 8:48 · 408 views
Leetcode 3698 | Split Array With Minimum Difference | With detailed explanation and dry run.Samrat Bhardwaj · 16:27 · 396 views
Weekly Contest 469 🔥 Leetcode 3698 | Split Array with Minimum Difference | Prefix Suffix Approach Study Placement · 16:32 · 181 views
The problem
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] <= 105
Approach overview
Problem 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.
Solution
We use a prefix sum array s to record the prefix sum of the array, where s[i] represents the sum of the array [0,..i]. Then we use two boolean arrays f and g to record the monotonicity of prefixes and suffixes respectively, where f[i] indicates whether the array [0,..i] is strictly increasing, and g[i] indicates whether the array [i,..n-1] is strictly decreasing.
Finally, we traverse array positions i where 0 leq i < n-1. If both f[i] and g[i+1] are true, then we can calculate the sums of left and right, which are s[i] and s[n-1]-s[i] respectively, and update the answer.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array.
class Solution:
def splitArray(self, nums: List[int]) -> int:
s = list(accumulate(nums))
n = len(nums)
f = [True] * n
for i in range(1, n):
f[i] = f[i - 1]
if nums[i] <= nums[i - 1]:
f[i] = False
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
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 -1class Solution {
public long splitArray(int[] nums) {
int n = nums.length;
long[] s = new long[n];
s[0] = nums[0];
boolean[] f = new boolean[n];
Arrays.fill(f, true);
boolean[] g = new boolean[n];
Arrays.fill(g, true);
for (int i = 1; i < n; ++i) {
s[i] = s[i - 1] + nums[i];
f[i] = f[i - 1];
if (nums[i] <= nums[i - 1]) {
f[i] = false;
}
}
for (int i = n - 2; i >= 0; --i) {
g[i] = g[i + 1];
if (nums[i] <= nums[i + 1]) {
g[i] = false;
}
}
final long inf = Long.MAX_VALUE;
long ans = inf;
for (int i = 0; i < n - 1; ++i) {
if (f[i] && g[i + 1]) {
long s1 = s[i];
long s2 = s[n - 1] - s[i];
ans = Math.min(ans, Math.abs(s1 - s2));
}
}
return ans < inf ? ans : -1;
}
}class Solution {
public:
long long splitArray(vector<int>& nums) {
int n = nums.size();
vector<long long> s(n);
s[0] = nums[0];
vector<bool> f(n, true), g(n, true);
for (int i = 1; i < n; ++i) {
s[i] = s[i - 1] + nums[i];
f[i] = f[i - 1];
if (nums[i] <= nums[i - 1]) {
f[i] = false;
}
}
for (int i = n - 2; i >= 0; --i) {
g[i] = g[i + 1];
if (nums[i] <= nums[i + 1]) {
g[i] = false;
}
}
const long long inf = LLONG_MAX;
long long ans = inf;
for (int i = 0; i < n - 1; ++i) {
if (f[i] && g[i + 1]) {
long long s1 = s[i];
long long s2 = s[n - 1] - s[i];
ans = min(ans, llabs(s1 - s2));
}
}
return ans < inf ? ans : -1;
}
};function splitArray(nums: number[]): number {
const n = nums.length;
const s: number[] = Array(n);
const f: boolean[] = Array(n).fill(true);
const g: boolean[] = Array(n).fill(true);
s[0] = nums[0];
for (let i = 1; i < n; ++i) {
s[i] = s[i - 1] + nums[i];
f[i] = f[i - 1];
if (nums[i] <= nums[i - 1]) {
f[i] = false;
}
}
for (let i = n - 2; i >= 0; --i) {
g[i] = g[i + 1];
if (nums[i] <= nums[i + 1]) {
g[i] = false;
}
}
const INF = Number.MAX_SAFE_INTEGER;
let ans = INF;
for (let i = 0; i < n - 1; ++i) {
if (f[i] && g[i + 1]) {
const s1 = s[i];
const s2 = s[n - 1] - s[i];
ans = Math.min(ans, Math.abs(s1 - s2));
}
}
return ans < INF ? ans : -1;
}func splitArray(nums []int) int64 {
n := len(nums)
s := make([]int64, n)
f := make([]bool, n)
g := make([]bool, n)
for i := range f {
f[i] = true
g[i] = true
}
s[0] = int64(nums[0])
for i := 1; i < n; i++ {
s[i] = s[i-1] + int64(nums[i])
f[i] = f[i-1]
if nums[i] <= nums[i-1] {
f[i] = false
}
}
for i := n - 2; i >= 0; i-- {
g[i] = g[i+1]
if nums[i] <= nums[i+1] {
g[i] = false
}
}
const inf = int64(^uint64(0) >> 1)
ans := inf
for i := 0; i < n-1; i++ {
if f[i] && g[i+1] {
s1 := s[i]
s2 := s[n-1] - s[i]
ans = min(ans, abs(s1-s2))
}
}
if ans < inf {
return ans
}
return -1
}
func abs(x int64) int64 {
if x < 0 {
return -x
}
return x
}Complexity analysis
| 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 |
Frequently asked questions
Is Split Array With Minimum Difference easy or hard?
Split Array With Minimum Difference is typically considered a Medium difficulty problem. The brute force idea is simple, but identifying the prefix sum optimization and maintaining monotonic helpers to achieve O(n) time requires stronger array problem-solving skills.
Split Array With Minimum Difference Python/Java solution
Implement the optimal solution by computing a prefix sum array and iterating through possible split indices. At each step, derive left and right partition sums from the prefix values and update the minimum difference. The same logic works in Python, Java, C++, Go, and TypeScript with O(n) time complexity.
How to solve Split Array With Minimum Difference in O(n)?
First compute the prefix sum array so you know the cumulative sum at each index. The total array sum lets you derive the right partition sum as total minus the prefix. Maintain monotonic helper arrays to track the best prefix values while scanning once through the array, allowing the minimum difference to be updated in constant time per split.
What is the best approach for Split Array With Minimum Difference?
The most efficient approach uses a prefix sum array combined with monotonic helper arrays to track optimal prefix values. This allows you to evaluate each split point in constant time after preprocessing. The overall complexity becomes O(n) time with O(n) extra space.
Is Split Array With Minimum Difference asked at Google/Amazon/Meta?
Array partitioning and prefix sum optimization problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of minimizing sum differences or balancing partitions are common because they test array traversal, prefix sums, and optimization techniques.
What data structure is used in Split Array With Minimum Difference?
The solution primarily uses arrays and a prefix sum structure. Additional helper arrays store monotonic prefix values to efficiently track the best candidates while scanning possible split positions.
What is the time complexity of Split Array With Minimum Difference?
The optimal solution runs in O(n) time using prefix sums and a single pass through the array. Building the prefix array takes O(n), and evaluating each split also takes O(1) per position. A naive brute force approach would take O(n^2) time because it recomputes sums repeatedly.