LeetCode Ts-3698. Split Array With Minimum Difference

    AllenLi
    CodingLeetCode Js-Array

    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.

    你給予一個整數陣列 nums。
將陣列拆分成兩個子陣列，左子陣列與右子陣列，且左子陣列為嚴格地遞增，右子陣列為嚴格地遞減。
回傳左子陣列與右子陣列的最小絕對差。如果不存在有效的拆分，則回傳 -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.background-color:#ggg'>

    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.

    Solution:
    這題在寫的時候，我腦袋想了幾個步驟分類，依序如下：
    1. 我們可以將陣列依序累加後存放到 prefix 中，假設 nums = [1, 2, 3, 4]，則 prefix[] 依序為：

    - index = 0 -> 0
- index = 1 -> 0 + 1 = 1
- index = 2 -> 0 + 1 + 2 = 3
- index = 3 -> 0 + 1 + 2 + 3 = 6
- index = 4 -> 0 + 1 + 2 + 3 + 4 = 10

    2. 我需要檢驗的機制，因為題目要求：

    - 確認左邊陣列 inc[i] = nums[0...i] 是否嚴格遞增。
- 確認右邊陣列 dec[i] = nums[i...n-1]是否嚴格遞減。

    3. 依序列出這些左右陣列的組合，並且在列出的同時做到：

    - 檢驗左右陣列的排序條件。
- 確認左右陣列各自加總後的差值。
- 如果至少有一個切點成立，則回傳最小差值，如果都不符合，則回傳 -1。

    Code 1: BigO(n)

    function splitArray(nums: number[]): number {
    let n: number = nums.length;
    let leftSum: number = 0;
    let rightSum: number = 0;
    let minDiff: number = Infinity;
    let found: boolean = false;

    const prefix: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    const inc: boolean[] = new Array(n).fill(true);
    for (let i = 1; i < n; i++) {
        inc[i] = inc[i - 1] && nums[i] > nums[i - 1];
    }

    const dec: boolean[] = new Array(n).fill(true);
    for (let i = n - 2; i >= 0; i--) {
        dec[i] = dec[i + 1] && nums[i] > nums[i + 1];
    }
    
    for (let i = 0; i < n - 1; i++) {
        if (!inc[i] || !dec[i + 1]) continue;

        leftSum = prefix[i + 1];
        rightSum = prefix[n] - prefix[i + 1];

        minDiff = Math.min(minDiff, Math.abs(leftSum - rightSum));
        found = true;
    }
    return found ? minDiff : -1;
};

    FlowChart:
    Example 1

    Input: nums = [1,3,2]

prefix [ 0, 1, 4, 6 ]
inc [ true, true, false ]
dec [ false, true, true ]

leftSum 1, rightSum 5, minDiff 4
leftSum 4, rightSum 2, minDiff 2
return minDiff = 2;

    Example 2

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

prefix [ 0, 1, 3, 7, 10 ]
inc [ true, true, true, false ]
dec [ false, false, true, true ]

leftSum 3, rightSum 7, minDiff 4
leftSum 7, rightSum 3, minDiff 4
return minDiff = 4;

    Example 3

    Input: nums = [3,1,2]

prefix [ 0, 3, 4, 6 ]
inc [ true, false, false ]
dec [ false, false, true ]
found = false
return found = -1;

    Related Posts