3507. Minimum Pair Removal to Sort Array I

Description

Given an array nums, you can perform the following operation any number of times:

Select the adjacent pair with the minimum sum in nums. If multiple such pairs exist, choose the leftmost one.
Replace the pair with their sum.

Return the minimum number of operations needed to make the array non-decreasing.

An array is said to be non-decreasing if each element is greater than or equal to its previous element (if it exists).

Example 1:

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

Output: 2

Explanation:

The pair (3,1) has the minimum sum of 4. After replacement, nums = [5,2,4].
The pair (2,4) has the minimum sum of 6. After replacement, nums = [5,6].

The array nums became non-decreasing in two operations.

Example 2:

Input: nums = [1,2,2]

Output: 0

Explanation:

The array nums is already sorted.

Constraints:

1 <= nums.length <= 50
-1000 <= nums[i] <= 1000

Solutions

Solution 1: Simulation

We define a function \(\text{is\_non\_decreasing}(a)\) to determine whether the array \(a\) is a non-decreasing array.

We use a loop until the array \(arr\) becomes a non-decreasing array. In each iteration of the loop, we find the minimum sum of adjacent element pairs in the array \(arr\) and record the index \(k\) of the left element of that pair. Then, we replace the left element with the sum of the pair and remove the right element. Finally, we return the number of operations.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

Python3JavaC++GoTypeScriptRust

class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        arr = nums[:]
        ans = 0

        def is_non_decreasing(a: List[int]) -> bool:
            for i in range(1, len(a)):
                if a[i] < a[i - 1]:
                    return False
            return True

        while not is_non_decreasing(arr):
            k = 0
            s = arr[0] + arr[1]
            for i in range(1, len(arr) - 1):
                t = arr[i] + arr[i + 1]
                if s > t:
                    s = t
                    k = i
            arr[k] = s
            arr.pop(k + 1)
            ans += 1
        return ans

class Solution {
    public int minimumPairRemoval(int[] nums) {
        List<Integer> arr = new ArrayList<>();
        for (int x : nums) {
            arr.add(x);
        }
        int ans = 0;
        while (!isNonDecreasing(arr)) {
            int k = 0;
            int s = arr.get(0) + arr.get(1);
            for (int i = 1; i < arr.size() - 1; ++i) {
                int t = arr.get(i) + arr.get(i + 1);
                if (s > t) {
                    s = t;
                    k = i;
                }
            }
            arr.set(k, s);
            arr.remove(k + 1);
            ++ans;
        }
        return ans;
    }

    private boolean isNonDecreasing(List<Integer> arr) {
        for (int i = 1; i < arr.size(); ++i) {
            if (arr.get(i) < arr.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    int minimumPairRemoval(vector<int>& nums) {
        vector<int> arr = nums;
        int ans = 0;

        while (!isNonDecreasing(arr)) {
            int k = 0;
            int s = arr[0] + arr[1];

            for (int i = 1; i < arr.size() - 1; ++i) {
                int t = arr[i] + arr[i + 1];
                if (s > t) {
                    s = t;
                    k = i;
                }
            }

            arr[k] = s;
            arr.erase(arr.begin() + (k + 1));
            ++ans;
        }

        return ans;
    }

private:
    bool isNonDecreasing(const vector<int>& arr) {
        for (int i = 1; i < (int) arr.size(); ++i) {
            if (arr[i] < arr[i - 1]) {
                return false;
            }
        }
        return true;
    }
};

func minimumPairRemoval(nums []int) int {
    arr := append([]int(nil), nums...)
    ans := 0

    isNonDecreasing := func(a []int) bool {
        for i := 1; i < len(a); i++ {
            if a[i] < a[i-1] {
                return false
            }
        }
        return true
    }

    for !isNonDecreasing(arr) {
        k := 0
        s := arr[0] + arr[1]

        for i := 1; i < len(arr)-1; i++ {
            t := arr[i] + arr[i+1]
            if s > t {
                s = t
                k = i
            }
        }

        arr[k] = s
        copy(arr[k+1:], arr[k+2:])
        arr = arr[:len(arr)-1]
        ans++
    }

    return ans
}

function minimumPairRemoval(nums: number[]): number {
    const arr = nums.slice();
    let ans = 0;
    const isNonDecreasing = (a: number[]): boolean => {
        for (let i = 1; i < a.length; i++) {
            if (a[i] < a[i - 1]) {
                return false;
            }
        }
        return true;
    };
    while (!isNonDecreasing(arr)) {
        let k = 0;
        let s = arr[0] + arr[1];
        for (let i = 1; i < arr.length - 1; ++i) {
            const t = arr[i] + arr[i + 1];
            if (s > t) {
                s = t;
                k = i;
            }
        }
        arr[k] = s;
        arr.splice(k + 1, 1);
        ans++;
    }
    return ans;
}

impl Solution {
    pub fn minimum_pair_removal(nums: Vec<i32>) -> i32 {
        let mut arr: Vec<i32> = nums.clone();
        let mut ans: i32 = 0;

        fn is_non_decreasing(a: &Vec<i32>) -> bool {
            for i in 1..a.len() {
                if a[i] < a[i - 1] {
                    return false;
                }
            }
            true
        }

        while !is_non_decreasing(&arr) {
            let mut k: usize = 0;
            let mut s: i32 = arr[0] + arr[1];
            for i in 1..arr.len() - 1 {
                let t: i32 = arr[i] + arr[i + 1];
                if s > t {
                    s = t;
                    k = i;
                }
            }
            arr[k] = s;
            arr.remove(k + 1);
            ans += 1;
        }

        ans
    }
}

3507. Minimum Pair Removal to Sort Array I

Description

Solutions

Solution 1: Simulation

Comments