4015. Split Array With Minimum Difference¶

4015. Split Array With Minimum Difference

Medium

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.

Example 1:

Input: nums = [1,3,2]

Output: 2

Explanation:

`i`	`left`	`right`	Validity	`left` sum	`right` sum	Absolute difference
0	[1]	[3, 2]	Yes	1	5	`\|1 - 5\| = 4`
1	[1, 3]	[2]	Yes	4	2	`\|4 - 2\| = 2`

Thus, the minimum absolute difference is 2.

Example 2:

Input: nums = [1,2,4,3]

Output: 4

Explanation:

`i`	`left`	`right`	Validity	`left` sum	`right` sum	Absolute difference
0	[1]	[2, 4, 3]	No	1	9	-
1	[1, 2]	[4, 3]	Yes	3	7	`\|3 - 7\| = 4`
2	[1, 2, 4]	[3]	Yes	7	3	`\|7 - 3\| = 4`

Thus, the minimum absolute difference is 4.

Example 3:

Input: nums = [3,1,2]

Output: -1

Explanation:

No valid split exists, so the answer is -1.

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Solution¶

class Solution {
    private boolean isInc[], isDec[];
    private long pref[], suff[];
    public long splitArray(int[] nums) {
        int n = nums.length;

        pref = new long[n];
        suff = new long[n];
        isInc = new boolean[n];
        isDec = new boolean[n];

        pref[0] = nums[0];
        for (int i = 1; i < n; i++)
            pref[i] = pref[i - 1] + nums[i];
        suff[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) 
            suff[i] = suff[i + 1] + nums[i];
        isInc[0] = true;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) 
                isInc[i] = isInc[i - 1] & true;
            else 
                isInc[i] = false;
        } 
        isDec[n - 1] = true;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] > nums[i + 1]) 
                isDec[i] = isDec[i + 1] & true;
            else 
                isDec[i] = false;
        }

        long mini = Long.MAX_VALUE / 10;;
        for (int i = 0; i < n - 1; i++) {
            if (isInc[i] == true && isDec[i + 1] == true) 
                mini = Math.min(mini, Math.abs(pref[i] - suff[i + 1]));
        }
        return mini == Long.MAX_VALUE / 10 ? -1 : mini; 
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]