3698. Split Array With Minimum Difference

Problem Statement

You are given an integer array nums.

Split the array into exactly two subarrays, left and right, such that left is strictly increasing and right is strictly decreasing.

Return the minimum possible absolute difference between the sums of left and right. If no valid split exists, return -1.

Solution

The core idea is to find a valid split point in the array. A valid split can occur at an index i, where nums[0...i-1] forms the left subarray and nums[i...n-1] forms the right subarray.

For a split to be valid, two conditions must be met:

1. The left subarray must be strictly increasing. This means nums[0] < nums[1] < ... < nums[i-1].
2. The right subarray must be strictly decreasing. This means nums[i] > nums[i+1] > ... > nums[n-1].

We can iterate through all possible split points from i = 1 to n-1. For each i, we check if the two conditions are met. If they are, we calculate the absolute difference between the sum of the left subarray and the sum of the right subarray and keep track of the minimum difference found so far.

To efficiently check the conditions, we can precompute two boolean arrays:

• is_increasing[i] will be true if nums[0...i] is strictly increasing.
• is_decreasing[i] will be true if nums[i...n-1] is strictly decreasing.

We can compute is_increasing with a single pass from left to right, and is_decreasing with a single pass from right to left.

After precomputation, we can iterate from i = 1 to n-1. A valid split exists at i if is_increasing[i-1] and is_decreasing[i] are both true. If a valid split is found, we calculate the sum of both parts. To do this efficiently, we can precompute prefix sums of the array.

Let prefix_sum[i] be the sum of nums[0...i].

• The sum of the left subarray (nums[0...i-1]) is prefix_sum[i-1].
• The sum of the right subarray (nums[i...n-1]) is prefix_sum[n-1] - prefix_sum[i-1].

The absolute difference is abs(prefix_sum[i-1] - (prefix_sum[n-1] - prefix_sum[i-1])).

We find the minimum such difference over all valid split points. If no valid split is found, we return -1.

The provided solution takes a slightly different, more direct approach. It first finds the first index mid_pos from the left where the increasing property is violated (nums[i] <= nums[i-1]). This mid_pos becomes a candidate for the start of the decreasing subarray.

1. If no such mid_pos is found, the entire array is strictly increasing. A valid split can only be made by putting the last element in the right subarray.
2. It then verifies that the subarray from mid_pos to the end is strictly decreasing. If not, no valid split is possible.
3. If mid_pos is at the beginning (mid_pos == 1), the first element must be in the left part and the rest in the right.
4. Otherwise, the split must happen around nums[mid_pos - 1] and nums[mid_pos]. There are two possibilities for nums[mid_pos - 1]: it can either belong to the left increasing part or the right decreasing part. The solution calculates the difference for both cases and returns the minimum. This handles the ambiguity of where the “peak” element nums[mid_pos - 1] should go.

class Solution {
public:
    long long splitArray(vector<int>& nums) {
        int mid_pos = -1;
        int n = nums.size();
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] <= nums[i-1]) {
                mid_pos = i;
                break;
            }
        }
        if (mid_pos == -1) {
            long long sum = std::accumulate(nums.begin(), nums.end(), 0LL);
            sum -= nums[n-1] * 2;
            return abs(sum);
        }

        // check from mid_pos to end is decreasing
        for (int i = mid_pos + 1; i < nums.size(); i++) {
            if (nums[i] >= nums[i-1]) {
                return -1;
            }
        }
        if (mid_pos == 1) {
            long long sum = std::accumulate(nums.begin(), nums.end(), 0LL);
            sum -= nums[0] * 2;
            return abs(sum);
        }

        // accumulate from 0 to mid_pos - 2
        long long sum1 = std::accumulate(nums.begin(), nums.begin() + mid_pos - 1, 0LL);
        // accumulate from mid_pos to end
        long long sum2 = std::accumulate(nums.begin() + mid_pos, nums.end(), 0LL);
        if (nums[mid_pos] == nums[mid_pos-1]) {
            return abs(sum1 + nums[mid_pos - 1] - sum2);
        }
        return min(abs(sum1 + nums[mid_pos - 1] - sum2), abs(sum1 - (sum2 + nums[mid_pos - 1])));
    }
};

Time Complexity

• Time: $O(n)$, where $n$ is the number of elements in nums. We iterate through the array a constant number of times.
• Space: $O(1)$, as we only use a few variables to store sums and indices.