2035. Partition Array Into Two Arrays to Minimize Sum Difference LeetCode Solution
In this guide, you will get 2035. Partition Array Into Two Arrays to Minimize Sum Difference LeetCode Solution with the best time and space complexity. The solution to Partition Array Into Two Arrays to Minimize Sum Difference problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Partition Array Into Two Arrays to Minimize Sum Difference solution in C++
- Partition Array Into Two Arrays to Minimize Sum Difference solution in Java
- Partition Array Into Two Arrays to Minimize Sum Difference solution in Python
- Additional Resources
Problem Statement of Partition Array Into Two Arrays to Minimize Sum Difference
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. To partition nums, put each element of nums into one of the two arrays.
Return the minimum possible absolute difference.
Example 1:
Input: nums = [3,9,7,3]
Output: 2
Explanation: One optimal partition is: [3,9] and [7,3].
The absolute difference between the sums of the arrays is abs((3 + 9) – (7 + 3)) = 2.
Example 2:
Input: nums = [-36,36]
Output: 72
Explanation: One optimal partition is: [-36] and [36].
The absolute difference between the sums of the arrays is abs((-36) – (36)) = 72.
Example 3:
Input: nums = [2,-1,0,4,-2,-9]
Output: 0
Explanation: One optimal partition is: [2,4,-9] and [-1,0,-2].
The absolute difference between the sums of the arrays is abs((2 + 4 + -9) – (-1 + 0 + -2)) = 0.
Constraints:
1 <= n <= 15
nums.length == 2 * n
-107 <= nums[i] <= 107
Complexity Analysis
- Time Complexity: O(n \cdot 2^{n/2})
- Space Complexity: O(2^{n/2})
2035. Partition Array Into Two Arrays to Minimize Sum Difference LeetCode Solution in C++
class Solution {
public:
int minimumDifference(vector<int>& nums) {
const int n = nums.size() / 2;
const int sum = accumulate(nums.begin(), nums.end(), 0);
const int goal = sum / 2;
const vector<int> lNums(nums.begin(), nums.begin() + n);
const vector<int> rNums(nums.begin() + n, nums.end());
int ans = INT_MAX;
vector<vector<int>> lSums(n + 1);
vector<vector<int>> rSums(n + 1);
dfs(lNums, 0, 0, 0, lSums);
dfs(rNums, 0, 0, 0, rSums);
for (int lCount = 0; lCount <= n; ++lCount) {
auto& l = lSums[lCount];
auto& r = rSums[n - lCount];
ranges::sort(r);
for (const int lSum : l) {
const int i = firstGreaterEqual(r, goal - lSum);
if (i < r.size()) {
const int sumPartOne = sum - lSum - r[i];
const int sumPartTwo = sum - sumPartOne;
ans = min(ans, abs(sumPartOne - sumPartTwo));
}
if (i > 0) {
const int sumPartOne = sum - lSum - r[i - 1];
const int sumPartTwo = sum - sumPartOne;
ans = min(ans, abs(sumPartOne - sumPartTwo));
}
}
}
return ans;
}
private:
void dfs(const vector<int>& arr, int i, int count, int path,
vector<vector<int>>& sums) {
if (i == arr.size()) {
sums[count].push_back(path);
return;
}
dfs(arr, i + 1, count + 1, path + arr[i], sums);
dfs(arr, i + 1, count, path, sums);
}
int firstGreaterEqual(const vector<int>& arr, int target) {
return ranges::lower_bound(arr, target) - arr.begin();
}
};
/* code provided by PROGIEZ */2035. Partition Array Into Two Arrays to Minimize Sum Difference LeetCode Solution in Java
class Solution {
public int minimumDifference(int[] nums) {
final int n = nums.length / 2;
final int sum = Arrays.stream(nums).sum();
final int goal = sum / 2;
final int[] lNums = Arrays.copyOfRange(nums, 0, n);
final int[] rNums = Arrays.copyOfRange(nums, n, nums.length);
int ans = Integer.MAX_VALUE;
List<Integer>[] lSums = new List[n + 1];
List<Integer>[] rSums = new List[n + 1];
for (int i = 0; i <= n; ++i) {
lSums[i] = new ArrayList<>();
rSums[i] = new ArrayList<>();
}
dfs(lNums, 0, 0, 0, lSums);
dfs(rNums, 0, 0, 0, rSums);
for (int lCount = 0; lCount <= n; ++lCount) {
List<Integer> l = lSums[lCount];
List<Integer> r = rSums[n - lCount];
Collections.sort(r);
for (final int lSum : l) {
final int i = firstGreaterEqual(r, goal - lSum);
if (i < r.size()) {
final int sumPartOne = sum - lSum - r.get(i);
final int sumPartTwo = sum - sumPartOne;
ans = Math.min(ans, Math.abs(sumPartOne - sumPartTwo));
}
if (i > 0) {
final int sumPartOne = sum - lSum - r.get(i - 1);
final int sumPartTwo = sum - sumPartOne;
ans = Math.min(ans, Math.abs(sumPartOne - sumPartTwo));
}
}
}
return ans;
}
private void dfs(int[] arr, int i, int count, int path, List<Integer>[] sums) {
if (i == arr.length) {
sums[count].add(path);
return;
}
dfs(arr, i + 1, count + 1, path + arr[i], sums);
dfs(arr, i + 1, count, path, sums);
}
private int firstGreaterEqual(List<Integer> arr, int target) {
final int i = Collections.binarySearch(arr, target);
return i < 0 ? -i - 1 : i;
}
}
// code provided by PROGIEZ2035. Partition Array Into Two Arrays to Minimize Sum Difference LeetCode Solution in Python
class Solution:
def minimumDifference(self, nums: list[int]) -> int:
n = len(nums) // 2
summ = sum(nums)
goal = summ // 2
lNums = nums[:n]
rNums = nums[n:]
ans = abs(sum(lNums) - sum(rNums))
lSums = [[] for _ in range(n + 1)]
rSums = [[] for _ in range(n + 1)]
def dfs(
arr: list[int],
i: int,
count: int,
path: int,
sums: list[list[int]]
):
if i == len(arr):
sums[count].append(path)
return
dfs(arr, i + 1, count + 1, path + arr[i], sums)
dfs(arr, i + 1, count, path, sums)
dfs(lNums, 0, 0, 0, lSums)
dfs(rNums, 0, 0, 0, rSums)
for lCount in range(n):
l = lSums[lCount]
r = rSums[n - lCount]
r.sort()
for lSum in l:
i = bisect_left(r, goal - lSum)
if i < len(r):
sumPartOne = summ - lSum - r[i]
sumPartTwo = summ - sumPartOne
ans = min(ans, abs(sumPartOne - sumPartTwo))
if i > 0:
sumPartOne = summ - lSum - r[i - 1]
sumPartTwo = summ - sumPartOne
ans = min(ans, abs(sumPartOne - sumPartTwo))
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.