Minimum Absolute Difference of Two Subarray Sums

mediumSave

ArrayBinary SearchPrefix Sum

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.

Example 1

Input

[
  "[3,1,2,4,3]"
]

Output

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.

Example 2

Input

[
  "[1,2]"
]

Output

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`.

Example 3

Input

[
  "[10,20,30,40]"
]

Output

Explanation. Consider splitting as `[10, 20, 30]` (sum = 60) and `[40]` (sum = 40). The absolute difference is `|60 - 40| = 20`. This is the minimum.

Example 4

Input

[
  "[-10,-20,10,20]"
]

Output

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.

Example 5

Input

[
  "[0,0,0,0,0]"
]

Output

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?

Constraints:

- The input array `nums` will have at least 2 elements. - `2 <= nums.length <= 10^5` - `-1000 <= nums[i] <= 1000`

Views: 2