Partition Array Into Two Arrays to Minimize Sum Difference

Hard
1466.

Partition Array Into Two Arrays to Minimize Sum Difference

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.

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 <= 15
  • nums.length == 2 * n
  • -10^7 <= nums[i] <= 10^7
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDifference = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 15
  • nums.length == 2 * n
  • -10^7 <= nums[i] <= 10^7

Hints for Partition Array Into Two Arrays to Minimize Sum Difference

  1. Hint 1

    Trying all C(30, 15) splits is about 155 million — too many. Split the array into its left and right halves instead.

  2. Hint 2

    If you take k elements from the left half, you must take n - k from the right half. Enumerate each half's subset sums grouped by size.

  3. Hint 3

    For each left subset sum a of size k, binary-search the sorted right sums of size n - k for the value that brings a + b closest to total / 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

  1. Let total be the sum of all elements. For the left half and the right half, list all subset sums grouped by subset size.
  2. Sort each size group of the right half.
  3. For each size k and each left sum a of that size, the difference is |total - 2(a + b)| for a right sum b of size n - k. Binary-search the right group for the first b with 2b >= total - 2a and check it and its predecessor.
  4. 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 n elements.
  • 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 best

Java

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