Minimum Pair Removal to Sort Array II - Practice Coding Problems

Minimum Pair Removal to Sort Array II - Problem

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

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 Case

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

› Output: 3

💡 Note: Step 1: Min pair is (2,1) with sum 3 → [4,3,3,5]. Step 2: Min pair is (3,3) with sum 6 → [4,6,5]. Step 3: Min pair is (4,6) with sum 10 → [10,5]. Now 10 > 5, so we need 1 more: Step 4: Only pair (10,5) → [15]. Total: 3 operations.

Example 2 — Already Sorted

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

› Output: 0

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

Example 3 — Reverse Order

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

› Output: 4

💡 Note: Always merge smallest adjacent sum: (2,1)→3: [5,4,3,3]. Then (3,3)→6: [5,4,6]. Then (4,6)→10: [5,10]. Then (5,10)→15: [15]. Total: 4 operations.

Constraints

1 ≤ nums.length ≤ 10³
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Unsorted array [4,2,1,3,5]

Process

Find minimum adjacent sum pairs and merge them

Output

Count of operations needed (3 operations)

Key Takeaway

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

Asked in

G Google 15 A Amazon 12 M Microsoft 8

The key insight is to repeatedly find and merge the adjacent pair with minimum sum until the array becomes non-decreasing. The optimal approach uses efficient simulation with O(n²) time complexity by scanning for minimum pairs in each iteration.

Common Approaches

Approach	Time	Space	Notes
✓ Priority Queue Optimization	O(n² log n)	O(n)	Use min-heap to efficiently track minimum sum pairs during simulation
Simulation with Tracking	O(n²)	O(1)	Optimize brute force with better tracking and early termination
Brute Force Simulation	O(n³)	O(1)	Repeatedly scan array to find minimum sum pair and merge

Priority Queue Optimization — Algorithm Steps

Build initial heap with all adjacent pairs
Extract minimum sum pair from heap
Merge the pair and update affected neighbors
Add new pairs to heap if created
Repeat until array is sorted

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Heap

Add all adjacent pairs to min-heap

Extract Min

Get minimum sum pair from heap top

Update

Merge pair and rebuild affected pairs

Code -

solution.c — C

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

typedef struct {
    long long sum;
    int idx;
} Pair;

typedef struct {
    Pair* data;
    int size;
    int capacity;
} MinHeap;

MinHeap* createHeap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->data = (Pair*)malloc(capacity * sizeof(Pair));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void heapifyUp(MinHeap* heap, int idx) {
    if (idx == 0) return;
    int parent = (idx - 1) / 2;
    if (heap->data[idx].sum < heap->data[parent].sum || 
        (heap->data[idx].sum == heap->data[parent].sum && heap->data[idx].idx < heap->data[parent].idx)) {
        Pair temp = heap->data[idx];
        heap->data[idx] = heap->data[parent];
        heap->data[parent] = temp;
        heapifyUp(heap, parent);
    }
}

void heapifyDown(MinHeap* heap, int idx) {
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    int smallest = idx;
    
    if (left < heap->size && (heap->data[left].sum < heap->data[smallest].sum ||
        (heap->data[left].sum == heap->data[smallest].sum && heap->data[left].idx < heap->data[smallest].idx))) {
        smallest = left;
    }
    
    if (right < heap->size && (heap->data[right].sum < heap->data[smallest].sum ||
        (heap->data[right].sum == heap->data[smallest].sum && heap->data[right].idx < heap->data[smallest].idx))) {
        smallest = right;
    }
    
    if (smallest != idx) {
        Pair temp = heap->data[idx];
        heap->data[idx] = heap->data[smallest];
        heap->data[smallest] = temp;
        heapifyDown(heap, smallest);
    }
}

void push(MinHeap* heap, long long sum, int idx) {
    if (heap->size >= heap->capacity) return;
    heap->data[heap->size].sum = sum;
    heap->data[heap->size].idx = idx;
    heapifyUp(heap, heap->size);
    heap->size++;
}

Pair pop(MinHeap* heap) {
    Pair result = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
    return result;
}

int solution(int* nums, int numsSize) {
    if (numsSize <= 1) return 0;
    
    int* arr = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        arr[i] = nums[i];
    }
    
    int size = numsSize;
    int operations = 0;
    
    while (1) {
        if (size <= 1) break;
        
        // Check if already non-decreasing
        int isSorted = 1;
        for (int i = 1; i < size; i++) {
            if (arr[i] < arr[i-1]) {
                isSorted = 0;
                break;
            }
        }
        
        if (isSorted) break;
        
        // Build heap of all adjacent pairs
        MinHeap* heap = createHeap(size);
        for (int i = 0; i < size - 1; i++) {
            long long sum = (long long)arr[i] + arr[i+1];
            push(heap, sum, i);
        }
        
        // Find valid minimum pair
        long long minSum;
        int idx;
        while (heap->size > 0) {
            Pair pair = pop(heap);
            minSum = pair.sum;
            idx = pair.idx;
            if (idx < size - 1 && (long long)arr[idx] + arr[idx+1] == minSum) {
                break;
            }
        }
        
        // Merge the pair
        arr[idx] = (int)minSum;
        for (int i = idx + 1; i < size - 1; i++) {
            arr[i] = arr[i + 1];
        }
        size--;
        operations++;
        
        free(heap->data);
        free(heap);
    }
    
    free(arr);
    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) {
        if (token[0] >= '0' && token[0] <= '9' || token[0] == '-') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

Up to O(n) operations, each extracting from heap O(log n) and updating O(n) pairs

⚠ Quadratic Growth

Space Complexity

O(n)

Priority queue stores up to O(n) adjacent pairs

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 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

Priority Queue Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler