Solution For Partition Array Into Two Arrays To Minimize Sum Difference

Problem Statement:

Given an array nums of integers, partition it into two (contiguous) subarrays left and right so that:

1. Every element in left is less than or equal to every element in right.
2. left and right have non-empty lengths.
3. left has the smallest possible size.

Return the length of left after such a partitioning.

Approach:

1. Sort the given array in increasing order.
2. Initialize an array leftSum[] of size n+1, and a variable totalSum = 0.
3. Traverse the sorted array and add the element to totalSum.
4. For each index i from 1 to n-1, calculate the leftSum[i] as the sum of the first i elements of the sorted array.
5. Initialize variables minDiff and leftSize to infinity.
6. Traverse the array from left to right.
7. For each index i from 1 to n-1, calculate the difference between the sum of the first i elements and the sum of the remaining elements (totalSum – leftSum[i]).
8. If the difference is less than or equal to minDiff, update minDiff and leftSize to the current values.
9. Return leftSize.

Code:

class Solution {
public:
int partitionDisjoint(vector<int>& nums) {
int n = nums.size();
vector<int> sortedNums(nums);
sort(sortedNums.begin(), sortedNums.end());
vector<int> leftSum(n+1, 0);
int totalSum = 0;
for(int i=0; i<n; i++) totalSum += nums[i];
for(int i=1; i<n; i++) leftSum[i] = leftSum[i-1] + sortedNums[i-1];
int minDiff = INT_MAX, leftSize = INT_MAX;
for(int i=1; i<n; i++){
int diff = totalSum - leftSum[i];
if(diff <= minDiff){
minDiff = diff;
leftSize = i;
}
}
return leftSize;
}
};

Time Complexity: O(n log n) – due to sorting the array.

Space Complexity: O(n) – used for the leftSum array.

Step by Step Implementation For Partition Array Into Two Arrays To Minimize Sum Difference

public int minDifference(int[] nums) {
        // sort the array
        Arrays.sort(nums);
        
        // get the length of the array
        int len = nums.length;
        
        // initialize the minimum difference to be the difference between the first and last elements in the array
        int minDiff = nums[len - 1] - nums[0];
        
        // iterate through the array, starting at the second element
        for (int i = 1; i < len; i++) {
            // calculate the difference between the current element and the previous element
            int diff = nums[i] - nums[i - 1];
            
            // if the difference is less than the current minimum difference, update the minimum difference
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
        
        // return the minimum difference
        return minDiff;
    }

def minSumDifference(arr): 

# Sort the given array 
arr.sort() 

# Initialize a variable to store 
# minimum sum difference 
min_diff = 10000

# Find the sum of array 
n = len(arr) 
sum = 0
for i in range(n): 
	sum += arr[i] 

# Consider an inversion point 
# and get the sum of left 
# and right subarray 
for i in range(n): 
	
	# get the sum of left subarray 
	left_sum = 0
	for j in range(i): 
		left_sum += arr[j] 
	
	# get the sum of right subarray 
	right_sum = 0
	for j in range(i + 1, n): 
		right_sum += arr[j] 
	
	# if the difference between 
	# the sum of left and right 
	# subarray is less than min_diff 
	# then update the min_diff 
	if abs((left_sum - right_sum)) < min_diff: 
		min_diff = abs(left_sum - right_sum) 

# return the min_diff 
return min_diff

var partitionArray = function(nums, target) {
    // initialize two empty arrays
    var arr1 = [];
    var arr2 = [];
    
    // iterate over nums
    for (var i = 0; i < nums.length; i++) {
        // if current num is less than target, add it to arr1
        if (nums[i] < target) {
            arr1.push(nums[i]);
        // if current num is greater than target, add it to arr2    
        } else {
            arr2.push(nums[i]);
        }
    }
    
    // return the arrays
    return [arr1, arr2];
};

int partition_array_into_two_arrays_to_minimize_sum_difference(vector &nums) {
    int sum = 0;
    for(int i = 0; i < nums.size(); i++) {
        sum += nums[i];
    }
    
    int target = sum / 2;
    vector> dp(nums.size()+1, vector(target+1, 0));
    
    for(int i = 1; i <= nums.size(); i++) {
        for(int j = 1; j <= target; j++) {
            if(nums[i-1] > j) {
                dp[i][j] = dp[i-1][j];
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1]);
            }
        }
    }
    
    return sum - 2*dp[nums.size()][target];
}

public class Solution {
    public int MinDifference(int[] nums) {
        // sort the array
        Array.Sort(nums);
        
        // initialize left and right sums
        int leftSum = 0;
        int rightSum = 0;
        
        // get the sum of the entire array
        foreach(int num in nums) {
            rightSum += num;
        }
        
        // initialize minimum difference to be the sum of the entire array
        int minDiff = rightSum;
        
        // iterate through the array
        // at each index, update the left and right sums
        // and update the minimum difference if necessary
        for(int i = 0; i < nums.Length - 1; i++) {
            leftSum += nums[i];
            rightSum -= nums[i];
            
            int diff = Math.Abs(leftSum - rightSum);
            if(diff < minDiff) {
                minDiff = diff;
            }
        }
        
        return minDiff;
    }
}