We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Pair Removal to Sort Array I

Number: 3773

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an array of integers, you can repeatedly replace the adjacent pair with the minimum sum (choosing the leftmost pair if there are ties) by their sum. The goal is to determine the minimum number of these operations required to make the array non-decreasing (each element is greater than or equal to its previous element).

Key Insights

  • The operation always selects the adjacent pair with the smallest sum.
  • After each operation, the array length decreases by one.
  • The simulation is straightforward due to the small constraint (array length up to 50).
  • A simple loop that repeats until the array is non-decreasing is efficient enough.
  • In each iteration, scanning the array to find the minimum sum adjacent pair is O(n).

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario (n is the initial length of the array). Space Complexity: O(n) for storing the array.

Solution

The solution simulates the exact operations described in the problem. The algorithm repeatedly:

  1. Checks if the current array is non-decreasing.
  2. If not, scans the array to find the adjacent pair with the minimum sum (choosing the leftmost in case of ties).
  3. Replaces the selected pair with their sum, reducing the length of the array.
  4. Increments the operation count. Since the maximum number of operations is n-1 (with n up to 50), this simulation approach is efficient.

The main data structure used is a list (or array) for holding the numbers, and a couple of simple loops to check sorted order and to find the minimum sum pair.

Code Solutions

# Python solution for Minimum Pair Removal to Sort Array I

def minimum_operations_to_sort(nums):
    # Function to check if the array is non-decreasing
    def is_non_decreasing(arr):
        for i in range(1, len(arr)):
            if arr[i] < arr[i - 1]:
                return False
        return True

    operations = 0  # Counter for the number of operations performed

    # Continue until the list is non-decreasing or has only one element
    while len(nums) > 1 and not is_non_decreasing(nums):
        min_sum = float('inf')
        min_index = 0
        # Find the adjacent pair with the minimum sum (leftmost tie breaker)
        for i in range(len(nums) - 1):
            pair_sum = nums[i] + nums[i + 1]
            if pair_sum < min_sum:
                min_sum = pair_sum
                min_index = i
        # Replace the found pair with their sum
        nums = nums[:min_index] + [min_sum] + nums[min_index + 2:]
        operations += 1  # Increment the operations count
    
    return operations

# Example usage:
print(minimum_operations_to_sort([5,2,3,1]))  # Output: 2
print(minimum_operations_to_sort([1,2,2]))    # Output: 0
← Back to All Questions