Minimum Pair Removal to Sort Array I

Introduction

The Minimum Pair Removal to Sort Array I problem is a useful array simulation problem that teaches an important programming concept: repeatedly modifying an array until it satisfies a required condition.

In this problem, we are given an integer array nums. We repeatedly select two adjacent elements whose sum is the smallest.

If several adjacent pairs have the same minimum sum, we must select the leftmost pair.

After selecting the pair:

Add the two elements.
Replace the pair with their sum.
The array becomes one element shorter.
Continue until the array is sorted in non-decreasing order.

The goal is to return the minimum number of operations required.

What Does Non-Decreasing Mean?

An array is called non-decreasing when every element is greater than or equal to the element before it.

For example:

[1, 2, 2, 5, 8]

is non-decreasing because:

1 <= 2
2 <= 2
2 <= 5
5 <= 8

However:

[1, 4, 3, 7]

is not sorted because:

4 > 3

So, for this problem, we continue performing operations until there is no pair where the left element is greater than the right element.

Understanding the Operation

Suppose we have:

[5, 2, 3, 1]

The adjacent pairs are:

(5, 2) → 7
(2, 3) → 5
(3, 1) → 4

The smallest sum is 4, so we select:

(3, 1)

and replace those two numbers with 4.

The array becomes:

[5, 2, 4]

The array is still not sorted because:

5 > 2

We again examine the adjacent pairs:

(5, 2) → 7
(2, 4) → 6

The minimum sum is 6, so we replace (2, 4) with 6.

Now the array becomes:

[5, 6]

This is non-decreasing because:

5 <= 6

Therefore, the answer is:

Example 1

Input

nums = [5, 2, 3, 1]

Operation 1

Adjacent pair sums:

5 + 2 = 7
2 + 3 = 5
3 + 1 = 4

Minimum sum:

Replace 3 and 1:

[5, 2, 4]

Operation 2

Adjacent pair sums:

5 + 2 = 7
2 + 4 = 6

Minimum sum:

Replace 2 and 4:

[5, 6]

The array is now sorted.

Therefore:

Output = 2

Example 2

Input

nums = [1, 2, 2]

The array is already non-decreasing:

1 <= 2 <= 2

No operation is required.

Therefore:

Output = 0

This is why checking whether the array is already sorted should be the first step.

Core Idea Behind the Solution

The solution can be broken into three simple tasks:

Check whether the current array is sorted.
Find the adjacent pair with the smallest sum.
Merge that pair and repeat.

We can implement this directly using the original array.

The variable size tells us how many elements are currently active in the array.

Every time two adjacent elements are merged, the active size decreases by one.

Checking Whether the Array Is Sorted

A helper method makes the code easier to understand:

private boolean isSorted(int[] nums, int n) {
    for (int pos = 1; pos < n; pos++) {
        if (nums[pos] < nums[pos - 1]) {
            return false;
        }
    }

    return true;
}

Let's understand it step by step.

We start from index 1 because every element needs to be compared with the element immediately before it.

For example:

Index:  0  1  2  3
Array: [1, 2, 2, 5]

We check:

nums[1] < nums[0]
nums[2] < nums[1]
nums[3] < nums[2]

If any comparison is true, the array is not sorted.

For example:

[1, 5, 3]

When we reach:

5 > 3

the condition:

nums[2] < nums[1]

becomes true.

Therefore, we return:

false

Finding the Minimum Adjacent Pair

Next, we need to find the adjacent pair with the smallest sum.

int minSum = Integer.MAX_VALUE;
int currentPosition = -1;

for (int pos = 1; pos < size; pos++) {
    int sum = nums[pos - 1] + nums[pos];

    if (sum < minSum) {
        minSum = sum;
        currentPosition = pos;
    }
}

Initially:

minSum = Integer.MAX_VALUE;

This gives us a very large starting value.

Then we examine every adjacent pair.

For:

[5, 2, 3, 1]

we calculate:

5 + 2 = 7
2 + 3 = 5
3 + 1 = 4

The smallest value becomes:

minSum = 4

and:

currentPosition = 3

The position represents the right element of the selected pair.

Why Does the Leftmost Rule Work?

The problem says that if multiple pairs have the same minimum sum, we must select the leftmost one.

Notice that we use:

if (sum < minSum)

rather than:

if (sum <= minSum)

This small difference is important.

Suppose the pair sums are:

4, 6, 4

The first 4 is the leftmost minimum.

When the second 4 is encountered, this condition:

sum < minSum

is false because:

4 < 4

is false.

Therefore, the first pair remains selected.

This automatically implements the leftmost minimum pair rule.

Merging the Selected Pair

After finding the minimum pair, we replace the first element of that pair with their sum.

For example:

[5, 2, 3, 1]

Suppose:

3 + 1 = 4

The array temporarily becomes:

[5, 2, 4, 1]

But we don't want the old 1 to remain.

So we shift all elements after the merged pair one position to the left.

nums[currentPosition - 1] = minSum;

for (int pos = currentPosition; pos < size - 1; pos++) {
    nums[pos] = nums[pos + 1];
}

size--;

After shifting:

[5, 2, 4, 1]

becomes:

[5, 2, 4]

The active size is then reduced:

size--;

Why Do We Need `size`?

A Java array has a fixed length.

For example:

int[] nums = {5, 2, 3, 1};

The array's physical length remains 4.

When we merge two elements, Java does not actually shrink the array.

Instead, we maintain our own variable:

int size = nums.length;

Initially:

size = 4

After one merge:

size = 3

After another merge:

size = 2

So size tells us how many positions currently contain meaningful data.

Corrected Java Implementation

The original code contains a few typographical and logical errors. Here is a clean version:

class Solution {

    private boolean isSorted(int[] nums, int n) {
        for (int pos = 1; pos < n; pos++) {
            if (nums[pos] < nums[pos - 1]) {
                return false;
            }
        }

        return true;
    }

    public int minimumPairRemoval(int[] nums) {
        int size = nums.length;
        int operations = 0;

        while (!isSorted(nums, size)) {

            int minSum = Integer.MAX_VALUE;
            int currentPosition = -1;

            // Find the leftmost adjacent pair
            // having the minimum sum.
            for (int pos = 1; pos < size; pos++) {
                int sum = nums[pos - 1] + nums[pos];

                if (sum < minSum) {
                    minSum = sum;
                    currentPosition = pos;
                }
            }

            // Replace the selected pair with its sum.
            nums[currentPosition - 1] = minSum;

            // Shift remaining elements to the left.
            for (int pos = currentPosition; pos < size - 1; pos++) {
                nums[pos] = nums[pos + 1];
            }

            // The array now contains one fewer active element.
            size--;

            operations++;
        }

        return operations;
    }
}

Important Errors in the Original Code

The code provided in the question has several issues that should be corrected.

1. Incorrect comparison operator

The original code contains something similar to:

if (nums[pos] &t; nums[pos - 1])

The intended Java comparison is:

if (nums[pos] < nums[pos - 1])

The < operator means "less than."

2. Incorrect `LinkedList` declaration

The original code contains:

List<Integer> list = new LinkedList><)_;

This is invalid Java syntax.

It would normally be:

List<Integer> list = new LinkedList<>();

However, the list is not actually needed for this solution.

Therefore, we simply remove it.

3. Incorrect loop variable update

The original shifting loop contains:

for (int pos = curr_pos; pos < size - 1; curr_pos++)

The problem is that pos never increases.

It should be:

for (int pos = curr_pos; pos < size - 1; pos++)

Otherwise, the loop can fail to terminate correctly.

This is a very common programming mistake: the variable used in the loop condition should normally be the variable being incremented.

Complete Dry Run

Let's trace the algorithm with:

nums = [5, 2, 3, 1]

Initially:

size = 4
operations = 0

The array is not sorted because:

5 > 2

Find minimum pair

5 + 2 = 7
2 + 3 = 5
3 + 1 = 4

Minimum:

Merge:

[5, 2, 4]

Now:

size = 3
operations = 1

Second iteration

The array is still not sorted:

5 > 2

Calculate pair sums:

5 + 2 = 7
2 + 4 = 6

Minimum:

Merge:

[5, 6]

Now:

size = 2
operations = 2

The array is sorted:

5 <= 6

The loop stops.

Final answer:

Another Example: Already Sorted Array

Consider:

nums = [1, 2, 2, 4]

The helper method checks:

1 <= 2
2 <= 2
2 <= 4

Everything is valid.

Therefore:

isSorted(nums, size)

returns:

true

The while loop never executes.

So:

operations = 0

and the answer is:

Example With Equal Minimum Sums

Consider:

nums = [3, 1, 2, 2]

Adjacent sums are:

3 + 1 = 4
1 + 2 = 3
2 + 2 = 4

The minimum sum is 3, so the middle pair is selected.

Now consider a case where two minimum sums are equal:

[2, 1, 1, 2]

Pair sums:

2 + 1 = 3
1 + 1 = 2
1 + 2 = 3

Here the minimum is unique.

For an equal minimum such as:

[1, 2, 1, 2]

the pair sums are:

1 + 2 = 3
2 + 1 = 3
1 + 2 = 3

All three sums are 3.

Because we update only when:

sum < minSum

the first pair remains selected.

That is exactly what the leftmost rule requires.

Time Complexity

Let n be the original length of the array.

During each operation, we scan the current array to find the minimum pair.

In the worst case, we may perform approximately n operations.

The scans therefore give a worst-case time complexity of approximately:

O(n²)

The shifting operation also takes linear time in the worst case, so the overall complexity remains:

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

The solution modifies the input array directly and uses only a few additional variables.

Why This Approach Is Beginner-Friendly

This solution closely follows the problem statement.

We can think of the algorithm as:

while array is not sorted:
    find smallest adjacent pair
    merge that pair
    count the operation

There is no complicated data structure or advanced algorithm required.

The most important programming concepts involved are:

Array traversal
Adjacent element comparison
Finding a minimum
Maintaining an active array size
Shifting array elements
Simulation
Helper methods
Time and space complexity

Key Takeaways

When solving Minimum Pair Removal to Sort Array I, remember these points:

Check whether the array is already non-decreasing.
If it is sorted, return 0.
Otherwise, examine every adjacent pair.
Select the pair with the smallest sum.
If sums are equal, keep the first pair found.
Replace the pair with their sum.
Shift the remaining elements to close the gap.
Decrease the active array size.
Increment the operation counter.
Repeat until the array becomes non-decreasing.

The key idea is simple: simulate exactly what the problem asks us to do, while keeping track of only the active portion of the array.

Final Summary

The Minimum Pair Removal to Sort Array I problem demonstrates how a seemingly simple array operation can require careful implementation.

The most important parts of the solution are the isSorted() helper method, the search for the minimum adjacent pair, the leftmost tie-breaking rule, and the manual shifting of elements after a merge.

Once these concepts are understood, the complete solution becomes much easier to follow and implement in Java.

Software and Programming concepts

3507. Minimum Pair Removal to Sort Array I

Minimum Pair Removal to Sort Array I