Partition Array Into Two Arrays to Minimize Sum Difference Solution
Partition Array Into Two Arrays to Minimize Sum Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Partition Array Into Two Arrays to Minimize Sum Difference is a hard coding problem on arrays, binary search and bit manipulation, asked in Amazon, Google and Arcesium interviews.
- Difficulty: Hard
- Topics: Arrays, Binary Search, Bit Manipulation, Bitmask
- Asked at: Amazon, Google, Arcesium
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums of length 2 · n. Split it into two arrays of length n each, so that every element goes to exactly one of them.
Return the minimum possible absolute difference between the sums of the two arrays.
Example 1
Input: nums = [5,1,8,2]
Output: 2
Explanation: Split into `[1,8]` and `[5,2]`: sums 9 and 7.
Example 2
Input: nums = [-40,40]
Output: 80
Example 3
Input: nums = [7,-3,4,1,-6,2]
Output: 1
Explanation: `[7,-6,1]` sums to 2 and `[-3,4,2]` sums to 3.
Constraints
1 <= n <= 15nums.length == 2 * n-10^7 <= nums[i] <= 10^7
Hints for Partition Array Into Two Arrays to Minimize Sum Difference
Hint 1
Trying all
C(30, 15)splits is about 155 million — too many. Split the array into its left and right halves instead.Hint 2
If you take
kelements from the left half, you must taken - kfrom the right half. Enumerate each half's subset sums grouped by size.Hint 3
For each left subset sum
aof sizek, binary-search the sorted right sums of sizen - kfor the value that bringsa + bclosest tototal / 2.
How to solve Partition Array Into Two Arrays to Minimize Sum Difference
Meet in the middle. Each half has only 2^n <= 32768 subsets. A partition picks k elements from the left half and n - k from the right; for a fixed left sum, the best right sum is found by binary search.
Approach
- Let
totalbe the sum of all elements. For the left half and the right half, list all subset sums grouped by subset size. - Sort each size group of the right half.
- For each size
kand each left sumaof that size, the difference is|total - 2(a + b)|for a right sumbof sizen - k. Binary-search the right group for the firstbwith2b >= total - 2aand check it and its predecessor. - Return the smallest difference found.
Why it works
Every partition corresponds to one left subset and one right subset whose sizes add up to n, and its difference is |total - 2·(a + b)|. For fixed a, that expression is minimised by the b closest to (total - 2a) / 2, which is one of the two neighbours of the binary-search position in the sorted group.
Complexity
- Time —
O(2^n · n) - Space —
O(2^n)
Pitfalls
- Group the right sums by size — mixing sizes breaks the requirement that each array has exactly
nelements. - Compare with integers (
2b >= total - 2a) rather than dividing by two, which goes wrong with odd or negative totals. - Check both the found position and the one before it.
Reference solution
Python
from typing import List
from bisect import bisect_left
def minimumDifference(nums: List[int]) -> int:
n = len(nums) // 2
total = sum(nums)
def sums(arr):
groups = [[] for _ in range(n + 1)]
for mask in range(1 << n):
s = 0
c = 0
for b in range(n):
if mask >> b & 1:
s += arr[b]
c += 1
groups[c].append(s)
return groups
left = sums(nums[:n])
right = sums(nums[n:])
for g in right:
g.sort()
best = None
for k in range(n + 1):
r = right[n - k]
for a in left[k]:
need = total - 2 * a
i = bisect_left(r, (need + 1) // 2)
for j in (i - 1, i):
if 0 <= j < len(r):
d = abs(need - 2 * r[j])
if best is None or d < best:
best = d
return bestJava
private static List<List<Long>> halfSumsMD(int[] nums, int off, int n) {
List<List<Long>> groups = new ArrayList<>();
for (int k = 0; k <= n; k++) groups.add(new ArrayList<>());
for (int mask = 0; mask < (1 << n); mask++) {
long s = 0;
for (int b = 0; b < n; b++) if ((mask >> b & 1) == 1) s += nums[off + b];
groups.get(Integer.bitCount(mask)).add(s);
}
return groups;
}
public static int minimumDifference(int[] nums) {
int n = nums.length / 2;
long total = 0;
for (int v : nums) total += v;
List<List<Long>> left = halfSumsMD(nums, 0, n), right = halfSumsMD(nums, n, n);
long[][] r = new long[n + 1][];
for (int k = 0; k <= n; k++) {
List<Long> g = right.get(k);
r[k] = new long[g.size()];
for (int i = 0; i < g.size(); i++) r[k][i] = g.get(i);
Arrays.sort(r[k]);
}
long best = Long.MAX_VALUE;
for (int k = 0; k <= n; k++) {
long[] R = r[n - k];
for (long a : left.get(k)) {
long need = total - 2 * a;
int lo = 0, hi = R.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (2 * R[mid] < need) lo = mid + 1; else hi = mid;
}
if (lo < R.length) best = Math.min(best, Math.abs(need - 2 * R[lo]));
if (lo > 0) best = Math.min(best, Math.abs(need - 2 * R[lo - 1]));
}
}
return (int) best;
}C++
static vector<vector<long long>> halfSumsMD(const vector<int>& nums, int off, int n) {
vector<vector<long long>> groups(n + 1);
for (int mask = 0; mask < (1 << n); mask++) {
long long s = 0;
for (int b = 0; b < n; b++) if (mask >> b & 1) s += nums[off + b];
groups[__builtin_popcount(mask)].push_back(s);
}
return groups;
}
int minimumDifference(vector<int>& nums) {
int n = nums.size() / 2;
long long total = 0;
for (int v : nums) total += v;
vector<vector<long long>> left = halfSumsMD(nums, 0, n), right = halfSumsMD(nums, n, n);
for (auto& g : right) sort(g.begin(), g.end());
long long best = LLONG_MAX;
for (int k = 0; k <= n; k++) {
const vector<long long>& R = right[n - k];
for (long long a : left[k]) {
long long need = total - 2 * a;
int lo = 0, hi = R.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (2 * R[mid] < need) lo = mid + 1; else hi = mid;
}
if (lo < (int)R.size()) best = min(best, llabs(need - 2 * R[lo]));
if (lo > 0) best = min(best, llabs(need - 2 * R[lo - 1]));
}
}
return (int)best;
}JavaScript
var minimumDifference = function(nums) {
var n = nums.length / 2;
var total = 0;
for (var i = 0; i < nums.length; i++) total += nums[i];
var sums = function(off) {
var groups = [];
for (var k = 0; k <= n; k++) groups.push([]);
for (var mask = 0; mask < (1 << n); mask++) {
var s = 0, c = 0;
for (var b = 0; b < n; b++) if (mask & (1 << b)) { s += nums[off + b]; c++; }
groups[c].push(s);
}
return groups;
};
var left = sums(0), right = sums(n);
for (var g = 0; g <= n; g++) right[g].sort(function(x, y) { return x - y; });
var best = Infinity;
for (var k2 = 0; k2 <= n; k2++) {
var R = right[n - k2];
for (var t = 0; t < left[k2].length; t++) {
var need = total - 2 * left[k2][t];
var lo = 0, hi = R.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (2 * R[mid] < need) lo = mid + 1; else hi = mid;
}
if (lo < R.length) best = Math.min(best, Math.abs(need - 2 * R[lo]));
if (lo > 0) best = Math.min(best, Math.abs(need - 2 * R[lo - 1]));
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search