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: Simulation

• Time complexity: O(n²)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const minimumPairRemoval = function (nums) {
  const current = [...nums];
  let result = 0;

  const isNonDecreasing = arr => {
    const n = arr.length;

    for (let index = 1; index < n; index++) {
      if (arr[index] < arr[index - 1]) return false;
    }

    return true;
  };

  while (!isNonDecreasing(current)) {
    const n = current.length;
    let minSum = Number.MAX_SAFE_INTEGER;
    let pair = -1;

    for (let index = 1; index < n; index++) {
      const sum = current[index] + current[index - 1];

      if (sum < minSum) {
        minSum = sum;
        pair = index - 1;
      }
    }

    current.splice(pair, 2, minSum);
    result += 1;
  }

  return result;
};