Minimum Absolute Difference of Two Subarray Sums
Given an array of integers nums, you need to split it into two non-empty subarrays, subarray1 and subarray2, such that the absolute difference between the sum of elements in subarray1 and the sum of elements in subarray2 is minimized. Return this minimum absolute difference. For example, if nums = [3, 1, 2, 4, 3], you can split it as [3, 1, 2] and [4, 3]. The sums would be 6 and 7, resulting in an absolute difference of |6 - 7| = 1. This is the minimum possible difference for this array.
[ "[3,1,2,4,3]" ]
Explanation. The array can be split in several ways. If we split it as `[3, 1, 2]` (sum = 6) and `[4, 3]` (sum = 7), the absolute difference is `|6 - 7| = 1`. This is the minimum possible difference.
[ "[1,2]" ]
Explanation. Only one way to split into two non-empty subarrays: `[1]` (sum = 1) and `[2]` (sum = 2). The absolute difference is `|1 - 2| = 1`.
[ "[10,20,30,40]" ]
Explanation. Consider splitting as `[10, 20, 30]` (sum = 60) and `[40]` (sum = 40). The absolute difference is `|60 - 40| = 20`. This is the minimum.
[ "[-10,-20,10,20]" ]
Explanation. The total sum is 0. If we split as `[-10]` (sum = -10) and `[-20, 10, 20]` (sum = 10), the absolute difference is `|-10 - 10| = |-20| = 20`. This is the minimum.
[ "[0,0,0,0,0]" ]
Explanation. Any split of an array of zeros will result in both subarrays having a sum of 0, leading to an absolute difference of 0.
Follow-up: Can you solve this problem if the array contained a very large number of elements (e.g., 10^6) and you needed to optimize for memory, perhaps without storing all prefix sums if they are very large?
- The input array `nums` will have at least 2 elements. - `2 <= nums.length <= 10^5` - `-1000 <= nums[i] <= 1000`
- Views
- 11