3507. Minimum Pair Removal to Sort Array I LeetCode Solution

In this guide, you will get 3507. Minimum Pair Removal to Sort Array I LeetCode Solution with the best time and space complexity. The solution to Minimum Pair Removal to Sort Array I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Pair Removal to Sort Array I solution in C++
4. Minimum Pair Removal to Sort Array I solution in Java
5. Minimum Pair Removal to Sort Array I solution in Python
6. Additional Resources

Problem Statement of Minimum Pair Removal to Sort Array I

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

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(n)

3507. Minimum Pair Removal to Sort Array I LeetCode Solution in C++

#include <ranges>

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

    while (hasInversion(nums)) {
      vector<int> pairSums;
      for (const auto& [a, b] : views::pairwise(nums))
        pairSums.push_back(a + b);
      const int minPairSum = ranges::min(pairSums);
      const int minPairIndex =
          ranges::find(pairSums, minPairSum) - pairSums.begin();
      nums[minPairIndex] = minPairSum;
      nums.erase(nums.begin() + minPairIndex + 1);
      ++ans;
    }

    return ans;
  }

 private:
  bool hasInversion(const vector<int>& nums) {
    for (const auto& [a, b] : views::pairwise(nums))
      if (a > b)
        return true;
    return false;
  }
};
/* code provided by PROGIEZ */

3507. Minimum Pair Removal to Sort Array I LeetCode Solution in Java

class Solution {
  public int minimumPairRemoval(int[] nums) {
    int ans = 0;
    List<Integer> numsList = Arrays.stream(nums).boxed().collect(Collectors.toList());

    while (hasInversion(numsList)) {
      List<Integer> pairSums = new ArrayList<>();
      for (int i = 0; i < numsList.size() - 1; ++i)
        pairSums.add(numsList.get(i) + numsList.get(i + 1));
      int minPairSum = Integer.MAX_VALUE;
      int minPairIndex = -1;
      for (int i = 0; i < pairSums.size(); ++i)
        if (pairSums.get(i) < minPairSum) {
          minPairSum = pairSums.get(i);
          minPairIndex = i;
        }
      numsList.set(minPairIndex, minPairSum);
      numsList.remove(minPairIndex + 1);
      ++ans;
    }

    return ans;
  }

  private boolean hasInversion(List<Integer> nums) {
    for (int i = 0; i < nums.size() - 1; ++i)
      if (nums.get(i) > nums.get(i + 1))
        return true;
    return false;
  }
}
// code provided by PROGIEZ

3507. Minimum Pair Removal to Sort Array I LeetCode Solution in Python

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

    while any(x > y for x, y in itertools.pairwise(nums)):
      pairSums = [x + y for x, y in itertools.pairwise(nums)]
      minPairSum = min(pairSums)
      minPairIndex = pairSums.index(minPairSum)
      nums[minPairIndex] = minPairSum
      nums.pop(minPairIndex + 1)
      ans += 1

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.