Partition Array Into Two Arrays To Minimize Sum Difference - Leetcode Solution

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.

1