Minimum Pair Removal to Sort Array I

easy linked list simulation array

Problem

You may repeat this operation any number of times: find the adjacent pair with the minimum sum (if several tie, take the leftmost), then replace those two elements with their sum. Return the minimum number of operations needed to make the array non-decreasing — that is, every element ≥ the one before it.

Inputnums = [5, 2, 3, 1]

Output2

Pair (3,1) sums to 4, the minimum → [5,2,4]. Then pair (2,4) sums to 6 → [5,6], which is non-decreasing. Two operations.

nums (comma-separated)

def minimumPairRemoval(nums):
    nums = list(nums)
    ops = 0
    while not is_sorted(nums):       # already non-decreasing? done
        best_i, best_sum = 0, nums[0] + nums[1]
        for i in range(1, len(nums) - 1):
            s = nums[i] + nums[i + 1]
            if s < best_sum:         # strictly smaller -> new leftmost min
                best_sum, best_i = s, i
        nums[best_i:best_i + 2] = [best_sum]   # merge the pair
        ops += 1
    return ops

def is_sorted(a):
    return all(a[i] <= a[i + 1] for i in range(len(a) - 1))

function minimumPairRemoval(nums) {
  nums = nums.slice();
  let ops = 0;
  while (!isSorted(nums)) {            // already non-decreasing? done
    let bestI = 0, bestSum = nums[0] + nums[1];
    for (let i = 1; i < nums.length - 1; i++) {
      const s = nums[i] + nums[i + 1];
      if (s < bestSum) {              // strictly smaller -> new leftmost min
        bestSum = s; bestI = i;
      }
    }
    nums.splice(bestI, 2, bestSum);    // merge the pair
    ops++;
  }
  return ops;
}

function isSorted(a) {
  for (let i = 0; i < a.length - 1; i++) if (a[i] > a[i + 1]) return false;
  return true;
}

int minimumPairRemoval(int[] arr) {
    List<Integer> nums = new ArrayList<>();
    for (int v : arr) nums.add(v);
    int ops = 0;
    while (!isSorted(nums)) {              // already non-decreasing? done
        int bestI = 0, bestSum = nums.get(0) + nums.get(1);
        for (int i = 1; i < nums.size() - 1; i++) {
            int s = nums.get(i) + nums.get(i + 1);
            if (s < bestSum) {            // strictly smaller -> leftmost min
                bestSum = s; bestI = i;
            }
        }
        nums.set(bestI, bestSum);          // merge the pair
        nums.remove(bestI + 1);
        ops++;
    }
    return ops;
}

boolean isSorted(List<Integer> a) {
    for (int i = 0; i < a.size() - 1; i++)
        if (a.get(i) > a.get(i + 1)) return false;
    return true;
}

int minimumPairRemoval(vector<int> nums) {
    int ops = 0;
    while (!isSorted(nums)) {              // already non-decreasing? done
        int bestI = 0, bestSum = nums[0] + nums[1];
        for (int i = 1; i + 1 < (int)nums.size(); i++) {
            int s = nums[i] + nums[i + 1];
            if (s < bestSum) {            // strictly smaller -> leftmost min
                bestSum = s; bestI = i;
            }
        }
        nums[bestI] = bestSum;             // merge the pair
        nums.erase(nums.begin() + bestI + 1);
        ops++;
    }
    return ops;
}

bool isSorted(const vector<int>& a) {
    for (int i = 0; i + 1 < (int)a.size(); i++)
        if (a[i] > a[i + 1]) return false;
    return true;
}

Explanation

Because the array is tiny (length ≤ 50) and each operation removes one element, we can just simulate the process directly. Every merge shrinks the array by one, so there can be at most n − 1 operations before only a single element remains, which is trivially sorted.

Each round has two parts. First we ask: is the array already non-decreasing? If yes, we are finished and return the running count ops. If not, we must perform another operation.

To pick the operation we scan all adjacent pairs (nums[i], nums[i+1]) and track the smallest sum. We compare with a strict <: a tie does not replace the current best, so the leftmost minimum pair naturally wins, exactly as the problem requires.

We then merge that pair: write the sum into position best_i and delete best_i + 1. Conceptually the array behaves like a linked list of values where merging two neighbours splices a node out, which is why this problem is tagged with linked lists and doubly-linked lists.

Walking the example [5, 2, 3, 1]: the pair sums are 7, 5, 4, so (3,1)=4 wins → [5, 2, 4]. Now sums are 7, 6, so (2,4)=6 wins → [5, 6], which is sorted. Two operations, matching the expected answer.

Time: O(n²) Space: O(n)