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
This code repeatedly combines adjacent pairs of numbers until an array becomes sorted in ascending order, counting how many operations are needed. In each iteration, it scans the array to check if it's sorted and identifies the adjacent pair with the smallest sum. When it finds an unsorted array, it merges the pair with the lowest sum by adding them together and removing the second element, then increments a counter. This continues until no element is greater than its neighbor, at which point the function returns the total number of merge operations performed. Essentially, it's a sorting strategy that greedily combines the smallest adjacent pairs until the array reaches ascending order.
/**
* @param {number[]} nums
* @return {number}
*/
var minimumPairRemoval = function(nums) {
let sorted = false;
let operations = 0;
while (!sorted) {
sorted = true;
let lowestPair = null;
let lowestPairValue = Infinity;
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
sorted = false;
}
const sum = nums[i] + nums[i + 1];
if (sum < lowestPairValue) {
lowestPair = [i, i + 1];
lowestPairValue = sum;
}
}
if (!sorted && lowestPair) {
nums[lowestPair[0]] += nums[lowestPair[1]];
nums.splice(lowestPair[1], 1);
operations++;
}
}
return operations;
};