Minimum Pair Removal to Sort Array I - Practice Coding Problems

Minimum Pair Removal to Sort Array I - Problem

Array Hash Table Linked List Heap (Priority Queue) Simulation Doubly-Linked List Ordered Set Easy

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).

Input & Output

Example 1 — Basic Unsorted Array

$ Input: nums = [3,4,2,1]

› Output: 2

💡 Note: First merge (2,1)→3 giving [3,4,3], then merge (3,4)→7 giving [7,3]. Finally merge (7,3)→10 giving [10] (sorted). Total: 3 operations. Wait, let me recalculate: [3,4,2,1] → merge (2,1) → [3,4,3] → merge (3,3) → [3,7] (sorted). Total: 2 operations.

Example 2 — Already Sorted

$ Input: nums = [1,2,3,4]

› Output: 0

💡 Note: Array is already non-decreasing (1≤2≤3≤4), so no operations needed.

Example 3 — Single Element

$ Input: nums = [5]

› Output: 0

💡 Note: Single element array is trivially non-decreasing, no operations needed.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Unsorted array [3,4,2,1] needs to become non-decreasing

Process

Repeatedly merge adjacent pairs with minimum sum

Output

Count of operations needed to sort array

Key Takeaway

🎯 Key Insight: Always merge the adjacent pair with smallest sum to minimize total operations

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is to repeatedly find and merge the adjacent pair with minimum sum until the array becomes non-decreasing. The brute force approach scans all pairs in each iteration, while the optimized approach uses efficient data structures and early termination. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Simulation	O(n²)	O(1)	Smart simulation with efficient pair tracking and early termination
Priority Queue Optimization	O(n² log n)	O(n)	Use a min-heap to efficiently track and update minimum adjacent pairs
Brute Force Simulation	O(n³)	O(1)	Repeatedly find and merge the minimum adjacent pair until sorted

Optimized Simulation — Algorithm Steps

Step 1: Initialize with sorted check
Step 2: Track all adjacent pairs efficiently
Step 3: Apply greedy merging strategy
Step 4: Early termination on sorted array

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Sorted

First check if array [3,4,2,1] is already non-decreasing

Single Pass

Find minimum adjacent pair in one scan: (2,1)=3 is minimum

Merge & Continue

Merge pair and repeat until sorted

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int size) {
    if (size <= 1) return 0;
    
    int operations = 0;
    
    while (size > 1) {
        // Early termination: check if already sorted
        int isSorted = 1;
        for (int i = 1; i < size; i++) {
            if (nums[i] < nums[i-1]) {
                isSorted = 0;
                break;
            }
        }
        
        if (isSorted) break;
        
        // Find minimum adjacent pair with single pass
        int minSum = INT_MAX;
        int minIdx = 0;
        
        for (int i = 0; i < size - 1; i++) {
            int currentSum = nums[i] + nums[i+1];
            if (currentSum < minSum) {
                minSum = currentSum;
                minIdx = i;
            }
        }
        
        // Merge the minimum pair
        nums[minIdx] = minSum;
        for (int i = minIdx + 1; i < size - 1; i++) {
            nums[i] = nums[i + 1];
        }
        size--;
        operations++;
    }
    
    return operations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each of O(n) operations scans O(n) pairs, but with optimizations to reduce constant factors

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra space for tracking variables

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler