2035. Partition Array Into Two Arrays to Minimize Sum Difference

HardBit ManipulationArrayTwo PointersBinary SearchDynamic ProgrammingBitmaskOrdered Set
Leetcode Link

Problem Description

The problem asks us to divide an even-sized integer array nums into two equal subarrays in such a way that the absolute difference between the sums of these subarrays is minimized. Essentially, given an array of 2 * n integers, we aim to distribute the numbers between two subarrays of size n, such that when we subtract the sum of one subarray from the other, the result (ignoring whether it's negative or positive) is as small as possible.

Intuition

The intuition behind the solution is to realize that this problem can be thought of as a variant of the subset sum problem, which is a classic computer science problem. The idea is to determine all possible sums of subsets for two halves of the array separately and then to find the two sums (one from each half) that, when combined, give us the closest sum to equal partitioning.

Here's the step-by-step approach:

  1. Since we need to partition nums into two arrays of equal length n, we can use the concept of bit masking to generate all subsets of the first half and the second half of nums. Each bit in the bitmask represents whether to include a particular element in the subset or not.

  2. We generate two dictionaries f and g, where each key corresponds to the number of elements in the subset and each value is a set containing all the possible sums with that number of elements for the first and second halves, respectively.

  3. After aggregating all subset sums for each half and for all possible subset sizes (from 0 to n), we sort the values in f and g, because we will perform a binary search next.

  4. The binary search is used to efficiently find the pairs of sums (one from f and one from g) that get us closest to half of the total sum. For every sum in f, we look for a sum in g such that when both are added, they are as close as possible to balancing each other out, minimizing the absolute difference.

  5. We perform this operation for all subset sizes and keep track of the minimum absolute difference found.

  6. Finally, we return the smallest absolute difference achieved through this process, which is the answer to the problem.

Learn more about Two Pointers, Binary Search, Dynamic Programming and Bitmask patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Solution Approach

The solution implements a bit manipulation strategy to generate all possible subset sums for both halves of the array, followed by a binary search to efficiently find the closest sums between two halves.

Here's how the solution approach works:

  1. Initialize: Define two dictionaries f and g. The key is the number of elements in the subset, and the set is all possible sums with that number of elements from the first and second halves, respectively.

  2. Bitmasking: Use bit manipulation to represent subsets. For every number i from 0 to 2^n - 1, iterate each bit position j to determine if it should be part of the subset. Use the operation (1 << j) to check if the j-th bit of i is set.

  3. Calculate Subset Sums: For every subset represented by i:

    • Initialize sum s and count cnt for the first half, and s1 and cnt1 for the second half.
    • If the j-th bit is set, we'll add the j-th element to our subset sum s or s1, and increment cnt or cnt1.
    • If not, we subtract it, as we want all possible subset sums, which include those with elements negated. This helps later to find pairs that sum up to zero difference.
    • Add the sum s to the set in f[cnt] and s1 to the set in g[cnt1] for tracking all sums with that subset size.

  4. Search For Minimum Difference: Initialize ans as infinity (or a suitably large number). This will hold the smallest absolute difference found.

  5. Sorting and Binary Search:

    • For each possible subset size i from 0 to n:
      • Sort the values in f[i] and g[n - i].
      • For each sum a in f[i], perform a binary search in the sorted sums in g[n - i] to find the smallest absolute difference from -a (we use -a because we're looking to cancel out the sum a). Store the lower bound index in potential candidates left and right.
      • Check the neighbors of the lower bound index to ensure the closest match is found. Update ans if a closer sum is found.

  6. Return The Result: After examining all subset sizes and their possible pairs of sums, return the smallest absolute difference stored in ans.

This approach leverages:

  • Bitmasking/Bit Manipulation: To generate all subsets.
  • Hash Tables (defaultdict(set)): To efficiently store and access subset sums.
  • Sorting & Binary Search: To quickly find the closest pair of sums between two sorted lists.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose our even-sized integer array nums is [1, 2, 1, 3]. Since the size of the array 2 * n is 4, each subarray will have a size of n equals 2.

  1. Initialize: We create two dictionaries, f and g, to store subset sums of the first half [1, 2] and second half [1, 3], respectively.

  2. Bitmasking: We will consider bitmasks from 0 to 2^2 - 1 = 3 in binary:

    • 00 represents an empty subset.
    • 01 represents subsets containing the first element.
    • 10 represents subsets containing the second element.
    • 11 represents subsets containing both elements.

  3. Calculate Subset Sums: Let's calculate the possible subset sums for both halves:

    • For f (first half [1, 2]):
      • For bitmask 00, s = 0, cnt = 0. Add 0 to f[0].
      • For bitmask 01, s = 1, cnt = 1. Add 1 to f[1].
      • For bitmask 10, s = 2, cnt = 1. Add 2 to f[1].
      • For bitmask 11, s = 3, cnt = 2. Add 3 to f[2].
    • For g (second half [1, 3]):
      • For bitmask 00, s1 = 0, cnt1 = 0. Add 0 to g[0].
      • For bitmask 01, s1 = 1, cnt1 = 1. Add 1 to g[1].
      • For bitmask 10, s1 = 3, cnt1 = 1. Add 3 to g[1].
      • For bitmask 11, s1 = 4, cnt1 = 2. Add 4 to g[2].

So now our dictionaries look like this: f = {0: {0}, 1: {1, 2}, 2: {3}} g = {0: {0}, 1: {1, 3}, 2: {4}}

  1. Search For Minimum Difference: We start with ans set to a large number, let's say infinity.

  2. Sorting and Binary Search:

    • We have two subset sizes to check, i = 0 and i = 1 (since subsets of size 2 would exceed the half size we're matching against).
    • For i = 0, we have f[0] = {0} and g[2] = {4}. Since g does not contain a 0, the minimum difference here is |0 - 4| = 4.
    • For i = 1, we have f[1] = {1, 2} and g[1] = {1, 3}. We sort both sets (though they're already sorted) and perform binary searches:
      • For a = 1 in f[1], binary search for -1 in g[1]. We find the closest sum in g[1] is 1 (difference of 0).
      • For a = 2 in f[1], binary search for -2 in g[1]. The closest sum in g[1] is 1 (difference of 1).
    • The smallest difference found is 0 when a = 1 from f[1] and the matching sum from g[1] is also 1.

  3. Return The Result: The smallest absolute difference found is 0, which is the result of our example problem. We have successfully divided the array into two subarrays, [1, 2] and [1, 3], with sums 3 and 4 respectively, and after negating elements to find subset sums, we managed to get the absolute difference to 0.

This example showcases the algorithm's capability to find a minimum difference between subsets through bitmasking, storing subset sums, sorting, and binary searching.

Solution Implementation

1from collections import defaultdict
2from math import inf
3
4class Solution:
5    def minimumDifference(self, nums):
6        """
7        Calculate the minimum absolute difference between the sum of numbers chosen 
8        from the first half and the sum of numbers chosen from the second half.
9        """
10        # n represents half the length of the nums array
11        n = len(nums) // 2
12      
13        # Initialize defaultdicts to store sums for different counts of selected numbers
14        first_half_sums = defaultdict(set)
15        second_half_sums = defaultdict(set)
16      
17        # Iterate over all possible subsets of both halves
18        for i in range(1 << n):
19            sum_first = count_first = 0
20            sum_second = count_second = 0
21          
22            # Calculate sum and count for the first and second halves
23            for j in range(n):
24                if (i & (1 << j)) != 0:
25                    sum_first += nums[j]
26                    count_first += 1
27                    sum_second += nums[n + j]
28                    count_second += 1
29                else:
30                    sum_first -= nums[j]
31                    sum_second -= nums[n + j]
32          
33            # Store the sums for the counts
34            first_half_sums[count_first].add(sum_first)
35            second_half_sums[count_second].add(sum_second)
36      
37        # Initialize answer to infinity (represents a very large value)
38        answer = inf
39      
40        # Iterate over all possible counts of elements in the subset
41        for i in range(n + 1):
42            sorted_first_half_sums = sorted(list(first_half_sums[i]))
43            sorted_second_half_sums = sorted(list(second_half_sums[n - i]))
44          
45            # Find the pair with minimum absolute difference
46            for a in sorted_first_half_sums:
47                left, right = 0, len(sorted_second_half_sums) - 1
48                target = -a
49              
50                # Perform binary search to find the closest sum in the second half to the target
51                while left < right:
52                    mid = (left + right) // 2
53                    if sorted_second_half_sums[mid] >= target:
54                        right = mid
55                    else:
56                        left = mid + 1
57              
58                # Update the answer with the new minimum if it's smaller
59                answer = min(answer, abs(a + sorted_second_half_sums[left]))
60              
61                # Check the previous element for a better minimum, if possible
62                if left > 0:
63                    answer = min(answer, abs(a + sorted_second_half_sums[left - 1]))
64      
65        # Return the final answer
66        return answer
67
1class Solution {
2    public int minimumDifference(int[] nums) {
3        // n represents half the length of the input array nums.
4        int n = nums.length >> 1;
5        // f and g are maps containing sets representing the sum of the subsets for the first and second halves of nums, respectively.
6        Map<Integer, Set<Integer>> sumSubsetsFirstHalf = new HashMap<>();
7        Map<Integer, Set<Integer>> sumSubsetsSecondHalf = new HashMap<>();
8
9        // Generate all possible sums for subsets of both halves and the count of elements in those subsets.
10        for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
11            int sumFirstHalf = 0, countFirstHalf = 0;
12            int sumSecondHalf = 0, countSecondHalf = 0;
13            for (int j = 0; j < n; ++j) {
14                if ((bitmask & (1 << j)) != 0) {
15                    sumFirstHalf += nums[j];
16                    ++countFirstHalf;
17                    sumSecondHalf += nums[n + j];
18                    ++countSecondHalf;
19                } else {
20                    sumFirstHalf -= nums[j];
21                    sumSecondHalf -= nums[n + j];
22                }
23            }
24            sumSubsetsFirstHalf.computeIfAbsent(countFirstHalf, k -> new HashSet<>()).add(sumFirstHalf);
25            sumSubsetsSecondHalf.computeIfAbsent(countSecondHalf, k -> new HashSet<>()).add(sumSecondHalf);
26        }
27
28        // Initialize the answer to the largest possible value to find the minimum.
29        int minimumDifference = Integer.MAX_VALUE;
30
31        // Find the pair of subset sums from the first and second halves that is closest to zero in difference.
32        for (int i = 0; i <= n; ++i) {
33            // Convert sets to lists and sort them for binary search.
34            List<Integer> sortedFirstHalfSums = new ArrayList<>(sumSubsetsFirstHalf.get(i));
35            List<Integer> sortedSecondHalfSums = new ArrayList<>(sumSubsetsSecondHalf.get(n - i));
36            Collections.sort(sortedFirstHalfSums);
37            Collections.sort(sortedSecondHalfSums);
38
39            // Use binary search to find the closest second half sum to negate the first half sum.
40            for (int a : sortedFirstHalfSums) {
41                // Binary search to find the closest sum in the second half.
42                int left = 0, right = sortedSecondHalfSums.size() - 1;
43                int target = -a;
44                while (left < right) {
45                    int mid = (left + right) >> 1;
46                    if (sortedSecondHalfSums.get(mid) >= target) {
47                        right = mid;
48                    } else {
49                        left = mid + 1;
50                    }
51                }
52                // Update the minimum difference if a closer pair is found.
53                minimumDifference = Math.min(minimumDifference, Math.abs(a + sortedSecondHalfSums.get(left)));
54                if (left > 0) {
55                    minimumDifference = Math.min(minimumDifference, Math.abs(a + sortedSecondHalfSums.get(left - 1)));
56                }
57            }
58        }
59
60        return minimumDifference;
61    }
62}
63
1class Solution {
2public:
3    int minimumDifference(vector<int>& nums) {
4        // We use half the size of the input array for convenience.
5        int halfSize = nums.size() >> 1; // Same as dividing by 2 using right-shift.
6
7        // f and g will store subsets sums for the first and second half respectively.
8        vector<vector<int>> sumFirstHalf(halfSize + 1), sumSecondHalf(halfSize + 1);
9
10        // Iterate over all possible subsets for both halves.
11        for (int subset = 0; subset < (1 << halfSize); ++subset) {
12            int sum1 = 0, count1 = 0;
13            int sum2 = 0, count2 = 0;
14
15            // Calculate the subsets sums and their sizes for both halves.
16            for (int j = 0; j < halfSize; ++j) {
17                if (subset & (1 << j)) {
18                    sum1 += nums[j]; // Add to sum for first half.
19                    ++count1; // Increment count for first half.
20                    sum2 += nums[halfSize + j]; // Add to sum for second half.
21                    ++count2; // Increment count for second half.
22                } else {
23                    sum1 -= nums[j]; // Subtract from sum for first half.
24                    sum2 -= nums[halfSize + j]; // Subtract from sum for second half.
25                }
26            }
27
28            // Store the calculated sums in f and g based on their respective counts.
29            sumFirstHalf[count1].push_back(sum1);
30            sumSecondHalf[count2].push_back(sum2);
31        }
32
33        // Sort the subsets sums for each possible count for easier lookup later.
34        for (int i = 0; i <= halfSize; ++i) {
35            sort(sumFirstHalf[i].begin(), sumFirstHalf[i].end());
36            sort(sumSecondHalf[i].begin(), sumSecondHalf[i].end());
37        }
38
39        // Initialize the answer with the largest possible integer value.
40        int answer = INT_MAX;
41
42        // Iterate over all pairs of subset from first and second halves.
43        for (int i = 0; i <= halfSize; ++i) {
44            for (int firstHalfSum : sumFirstHalf[i]) {
45                int target = -firstHalfSum; // We want to find the closest to -firstHalfSum in second half.
46
47                // Binary search for the closest value in the second half with complementing size.
48                int left = 0, right = sumSecondHalf[halfSize - i].size() - 1;
49                while (left < right) {
50                    int mid = (left + right) >> 1;
51                    if (sumSecondHalf[halfSize - i][mid] >= target)
52                        right = mid;
53                    else
54                        left = mid + 1;
55                }
56              
57                // Update answer with the closest match before or at the binary search result.
58                answer = min(answer, abs(firstHalfSum + sumSecondHalf[halfSize - i][left]));
59                if (left > 0)
60                    answer = min(answer, abs(firstHalfSum + sumSecondHalf[halfSize - i][left - 1]));
61            }
62        }
63      
64        // Return the minimum difference found.
65        return answer;
66    }
67};
68
1// Assume this is the format of the input array of numbers.
2let nums: number[] = [];
3
4// Calculate the minimum absolute difference between the sum of any two subsets.
5function minimumDifference(nums: number[]): number {
6    // Use half the size of the input array for convenience.
7    let halfSize: number = nums.length >> 1; // Same as dividing by 2 using right-shift.
8
9    // sumFirstHalf and sumSecondHalf will store subset sums for the first and second half respectively.
10    let sumFirstHalf: number[][] = Array.from({ length: halfSize + 1 }, () => []);
11    let sumSecondHalf: number[][] = Array.from({ length: halfSize + 1 }, () => []);
12
13    // Iterate over all possible subsets for both halves.
14    for (let subset = 0; subset < (1 << halfSize); ++subset) {
15        let sum1 = 0, count1 = 0;
16        let sum2 = 0, count2 = 0;
17
18        // Calculate the subset sums and their sizes for both halves.
19        for (let j = 0; j < halfSize; ++j) {
20            if (subset & (1 << j)) {
21                sum1 += nums[j]; // Add to sum for first half.
22                ++count1; // Increment count for first half.
23                sum2 += nums[halfSize + j]; // Add to sum for second half.
24                ++count2; // Increment count for second half.
25            } else {
26                sum1 -= nums[j]; // Subtract from sum for first half.
27                sum2 -= nums[halfSize + j]; // Subtract from sum for second half.
28            }
29        }
30
31        // Store the calculated sums in sumFirstHalf and sumSecondHalf based on their respective counts.
32        sumFirstHalf[count1].push(sum1);
33        sumSecondHalf[count2].push(sum2);
34    }
35
36    // Sort the subset sums for each possible count for easier lookup later.
37    sumFirstHalf.forEach(subset => subset.sort((a, b) => a - b));
38    sumSecondHalf.forEach(subset => subset.sort((a, b) => a - b));
39
40    // Initialize the answer with the largest possible number value.
41    let answer: number = Number.MAX_SAFE_INTEGER;
42
43    // Iterate over all pairs of subsets from first and second halves.
44    for (let i = 0; i <= halfSize; ++i) {
45        for (let firstHalfSum of sumFirstHalf[i]) {
46            let target = -firstHalfSum; // We want to find the closest to -firstHalfSum in second half.
47
48            // Binary search for the closest value in the second half with complementing size.
49            let left = 0, right = sumSecondHalf[halfSize - i].length - 1;
50            while (left < right) {
51                let mid = (left + right) >> 1;
52                if (sumSecondHalf[halfSize - i][mid] >= target)
53                    right = mid;
54                else
55                    left = mid + 1;
56            }
57          
58            // Update answer with the closest match before or at the binary search result.
59            answer = Math.min(answer, Math.abs(firstHalfSum + sumSecondHalf[halfSize - i][left]));
60            if (left > 0)
61                answer = Math.min(answer, Math.abs(firstHalfSum + sumSecondHalf[halfSize - i][left - 1]));
62        }
63    }
64  
65    // Return the minimum difference found.
66    return answer;
67}
68
Not Sure What to Study? Take the 2-min Quiz

In a binary min heap, the maximum element can be found in:

Time and Space Complexity

The provided Python code defines a function minimumDifference which finds the minimum absolute difference between the sum of numbers chosen from two halves of an array. The function uses bitmasking to generate all possible subsets and their sums for each half of the input array, and then performs a binary search to find the minimum difference. Here's the analysis of both time and space complexity:

Time Complexity

  1. There are two loops iterating over (1 << n) subsets (where n is half the length of the input list), which gives us O(2^n) for generating all possible sums.
  2. Within each iteration of the first loop, it performs bits-checking and sum operations that run in O(n) time. Combined with the loop, this is O(n * 2^n).
  3. The sorting of f[i] and g[n - i] subsets can take O(2^n * log(2^n)), which simplifies to O(n * 2^n) because there are 2^n subsets for each i.
  4. The final loop iterates O(n) times, and within it, a binary search is performed on sorted lists. Each binary search takes O(log(2^n)) which simplifies to O(n). Thus, this part takes O(n^2).

The overall time complexity is the sum of these parts. However, the dominant factor is the generation of subsets and the sorting of the subsets, which both have O(n * 2^n) complexity. Therefore, the total time complexity is O(n * 2^n).

Space Complexity

  1. We are using two dictionaries f and g to store sums of subsets, which can at most have O(2^n) elements since we are storing sums for all possible subsets.
  2. For each subset sum, we might store up to n different sums due to different counts of integers included in the sums. Hence, this adds up to O(n * 2^n) space for each dictionary.
  3. The space needed for sorting and other variables is negligible compared to the space needed to store the subsets.

Thus, the total space complexity is O(n * 2^n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«