What is the time complexity of LeetCode 2035. Partition Array Into Two Arrays to Minimize Sum Difference?

The Python solution on this page runs in O(n) (after optional sort O(n log n)).

What is the space complexity of LeetCode 2035. Partition Array Into Two Arrays to Minimize Sum Difference?

The Python solution on this page uses O(1) auxiliary space.

Partition Array Into Two Arrays to Minimize Sum Difference — LeetCode 2035 Python Solution

HardBit ManipulationArrayTwo PointersBinary SearchDynamic ProgrammingBitmaskOrdered Set

Problem: #2035
Pattern: Bit Manipulation
Reading time: 6 min
Source: leetcode.com

The problem

You are given an integer array nums of 2 * n integers. You need to partition nums into two arrays of length n to minimize the absolute difference of the sums of the arrays.

Example

Input: nums = [3,9,7,3]
Output: 2
Explanation: One optimal partition is: [3,9] and [7,3].

Python solution

Python

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) >> 1
        f = defaultdict(set)
        g = defaultdict(set)
        for i in range(1 << n):
            s = cnt = 0
            s1 = cnt1 = 0
            for j in range(n):
                if (i & (1 << j)) != 0:
                    s += nums[j]
                    cnt += 1
                    s1 += nums[n + j]
                    cnt1 += 1
                else:
                    s -= nums[j]
                    s1 -= nums[n + j]
            f[cnt].add(s)
            g[cnt1].add(s1)

        ans = inf
        for i in range(n + 1):
            fi, gi = sorted(list(f[i])), sorted(list(g[n - i]))
            # min(abs(f[i] + g[n - i]))
            for a in fi:
                left, right = 0, len(gi) - 1
                b = -a
                while left < right:
                    mid = (left + right) >> 1
                    if gi[mid] >= b:
                        right = mid
                    else:
                        left = mid + 1
                ans = min(ans, abs(a + gi[left]))
                if left > 0:
                    ans = min(ans, abs(a + gi[left - 1]))
        return ans

Complexity

Measure	Complexity
Time	O(n) (after optional sort O(n log n))
Space	O(1) auxiliary

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2035. Partition Array Into Two Arrays to Minimize Sum Difference is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Bit Manipulation and Bitmask.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2035. Partition Array Into Two Arrays to Minimize Sum Difference?: LeetCode 2035. Partition Array Into Two Arrays to Minimize Sum Difference is rated Hard on LeetCode.
What is the time complexity of LeetCode 2035. Partition Array Into Two Arrays to Minimize Sum Difference?: The Python solution on this page runs in O(n) (after optional sort O(n log n)).
What is the space complexity of LeetCode 2035. Partition Array Into Two Arrays to Minimize Sum Difference?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2035. Partition Array Into Two Arrays to Minimize Sum Difference cover?: LeetCode 2035. Partition Array Into Two Arrays to Minimize Sum Difference is tagged Bit Manipulation, Array, Two Pointers, Binary Search, Dynamic Programming, Bitmask and Ordered Set on LeetCode.