LeetCode 2856 - Minimum Array Length After Pair Removals

This problem gives us a sorted integer array nums in non-decreasing order. We may repeatedly remove pairs of elements under one important rule: for a chosen pair (i, j), the values must satisfy nums[i] < nums[j].

leetcodemediumarrayhash-tabletwo-pointersbinary-searchgreedycounting

LeetCode Problem 2856

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Two Pointers, Binary Search, Greedy, Counting

Solution

Problem Understanding

This problem gives us a sorted integer array nums in non-decreasing order. We may repeatedly remove pairs of elements under one important rule: for a chosen pair (i, j), the values must satisfy nums[i] < nums[j]. In other words, the two chosen numbers cannot be equal, and the smaller one must come before the larger one in value.

After removing the two elements, the remaining elements stay in order and are re-indexed. We may continue performing removals as many times as possible, and our goal is to minimize the final array length.

Restating the problem more intuitively, we want to maximize the number of valid pairs we can remove. Since every operation removes exactly two elements, minimizing the remaining length is equivalent to maximizing the number of removals.

The input array is already sorted, which is an extremely important constraint. Since the numbers are ordered, we can reason about pairing smaller values with larger values efficiently. We do not need to reorder the array or search arbitrarily for valid pairs.

The constraints are large:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

An O(n²) algorithm would be too slow for n = 100000, since it could require around 10^10 operations in the worst case. This strongly suggests we need an O(n log n) or O(n) solution.

There are several important edge cases to consider:

  • Arrays where all numbers are identical, such as [5,5,5]. Since no element is strictly smaller than another, no removals are possible.
  • Arrays where all elements can pair perfectly, such as [1,2,3,4]. Every element can be matched with a larger one, producing a final length of 0.
  • Arrays with a dominant repeated value, such as [4,4,4,4,5]. Only one 4 can pair with 5, leaving many leftovers.
  • Arrays of length 1, where pairing is impossible.
  • Odd-length arrays, where even perfect pairing may still leave one element behind.

Approaches

Brute Force Approach

A brute-force strategy would repeatedly search for any valid pair (i, j) such that nums[i] < nums[j], remove them, then continue until no more pairs exist.

One way to implement this would be:

  1. Scan all possible pairs.
  2. Pick a valid pair.
  3. Remove both elements.
  4. Repeat until no valid pair remains.

This eventually produces the correct answer because it simulates the allowed operations directly. However, repeatedly searching and removing elements is extremely inefficient. Array removals themselves are expensive because elements shift after deletion.

In the worst case, each operation could cost O(n) for scanning and another O(n) for deletion, repeated up to O(n) times, leading to roughly O(n²) or worse performance.

Given the input size of 10^5, this is far too slow.

Key Insight for an Optimal Solution

The crucial observation is that the array is already sorted.

Since valid pairs require nums[i] < nums[j], every successful pairing must connect a smaller number with a strictly larger number.

To maximize removals, we should greedily match the smallest available numbers with the smallest larger numbers that can accept them.

A useful way to think about this is splitting the array into two halves:

  • The left half contains candidate smaller values.
  • The right half contains candidate larger values.

We try to match each left-side element with the earliest valid larger element.

Because the array is sorted, if nums[left] < nums[right], then pairing them is always safe and beneficial. We advance both pointers. Otherwise, if the values are equal, the current right value cannot match the current left value, so we move right forward to find something larger.

This greedy pairing guarantees the maximum number of removable pairs.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Simulates removals directly, too slow for large input
Optimal Two Pointers O(n) O(1) Greedily pairs smaller and larger elements

Algorithm Walkthrough

Optimal Greedy Two-Pointer Algorithm

  1. Let n be the length of the array.
  2. Initialize two pointers:
  • left = 0, representing the smaller element candidate.
  • right = (n + 1) // 2, representing the larger element candidate.

We start right in the second half because each valid pair needs one small element and one larger element. 3. Initialize pairs = 0 to count how many successful removals we can make. 4. While both pointers are inside the array:

  • If nums[left] < nums[right], we found a valid removable pair.

  • Increment pairs.

  • Move both pointers forward.

  • Otherwise, the values are equal, or right is not strictly larger.

  • Move right forward only.

This works because the array is sorted. If the current right value cannot pair with nums[left], no earlier right value can either. 5. After processing, each pair removes two elements. 6. Return:

$$n - 2 \times pairs$$

This gives the minimum remaining length.

Why it works

The key invariant is that we always try to match the smallest unmatched element with the smallest possible larger element. Since the array is sorted, using the earliest valid partner is optimal because it preserves larger values for future pairings.

If a larger element can pair with the current smallest unmatched value, delaying the pairing would never improve the result. The greedy choice never blocks a better solution later, which guarantees the maximum number of removable pairs.

Python Solution

from typing import List

class Solution:
    def minLengthAfterRemovals(self, nums: List[int]) -> int:
        n = len(nums)

        left = 0
        right = (n + 1) // 2
        pairs = 0

        while left < n // 2 and right < n:
            if nums[left] < nums[right]:
                pairs += 1
                left += 1
                right += 1
            else:
                right += 1

        return n - 2 * pairs

The implementation follows the greedy two-pointer strategy exactly.

We first compute the array length and initialize two pointers. The left pointer starts at the beginning because those values act as the smaller candidates. The right pointer starts in the second half so that we attempt to pair smaller values with larger ones.

Inside the loop, we compare nums[left] and nums[right].

If the right value is strictly larger, we form a valid pair and move both pointers forward. We also increment pairs because one removal operation has been completed.

If the values are equal, pairing is invalid because the problem requires strict inequality. Since the array is sorted, moving right forward is the only useful action.

Finally, every pair removes exactly two elements, so we subtract 2 * pairs from the original length.

Go Solution

func minLengthAfterRemovals(nums []int) int {
	n := len(nums)

	left := 0
	right := (n + 1) / 2
	pairs := 0

	for left < n/2 && right < n {
		if nums[left] < nums[right] {
			pairs++
			left++
			right++
		} else {
			right++
		}
	}

	return n - 2*pairs
}

The Go implementation mirrors the Python logic closely. Since Go slices already manage dynamic indexing, there is no special handling needed for arrays versus slices.

Integer overflow is not a concern here because the array length is at most 100000, and all calculations remain well within Go's integer range.

Unlike Python, Go does not distinguish between nil and empty slices in a way that matters here. The problem guarantees at least one element, so no special guard is required.

Worked Examples

Example 1

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

Initial setup:

  • n = 4
  • left = 0
  • right = 2
  • pairs = 0
Step left right Compare Action pairs
1 0 2 1 < 3 Pair formed 1
2 1 3 2 < 4 Pair formed 2

Final result:

$$4 - (2 \times 2) = 0$$

Example 2

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

Initial setup:

  • n = 6
  • left = 0
  • right = 3
Step left right Compare Action pairs
1 0 3 1 < 2 Pair formed 1
2 1 4 1 < 3 Pair formed 2
3 2 5 2 < 3 Pair formed 3

Final result:

$$6 - (2 \times 3) = 0$$

Example 3

Input: nums = [1000000000,1000000000]

Step left right Compare Action pairs
1 0 1 1000000000 < 1000000000 Invalid, move right 0

Final result:

$$2 - (2 \times 0) = 2$$

Example 4

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

Initial setup:

  • n = 5
  • left = 0
  • right = 3
Step left right Compare Action pairs
1 0 3 2 < 4 Pair formed 1
2 1 4 3 < 4 Pair formed 2

Final result:

$$5 - (2 \times 2) = 1$$

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each pointer moves at most n times
Space O(1) Only a few variables are used

The time complexity is linear because both pointers move forward monotonically and never backtrack. Even though there are two pointers, the total number of iterations is bounded by O(n).

The space complexity is constant because we only store a handful of integer variables regardless of input size.

Test Cases

class Solution:
    def minLengthAfterRemovals(self, nums):
        n = len(nums)

        left = 0
        right = (n + 1) // 2
        pairs = 0

        while left < n // 2 and right < n:
            if nums[left] < nums[right]:
                pairs += 1
                left += 1
                right += 1
            else:
                right += 1

        return n - 2 * pairs

sol = Solution()

assert sol.minLengthAfterRemovals([1, 2, 3, 4]) == 0  # basic perfect pairing
assert sol.minLengthAfterRemovals([1, 1, 2, 2, 3, 3]) == 0  # duplicates with full pairing
assert sol.minLengthAfterRemovals([1000000000, 1000000000]) == 2  # identical values
assert sol.minLengthAfterRemovals([2, 3, 4, 4, 4]) == 1  # odd length with leftovers

assert sol.minLengthAfterRemovals([5]) == 1  # single element
assert sol.minLengthAfterRemovals([5, 5, 5]) == 3  # all equal
assert sol.minLengthAfterRemovals([1, 2]) == 0  # smallest removable pair
assert sol.minLengthAfterRemovals([2, 2]) == 2  # smallest non-removable pair
assert sol.minLengthAfterRemovals([1, 1, 1, 2]) == 2  # one larger value
assert sol.minLengthAfterRemovals([1, 2, 2, 2, 3]) == 1  # repeated middle values
assert sol.minLengthAfterRemovals([1, 1, 1, 1, 2, 2]) == 2  # dominant repeated number
assert sol.minLengthAfterRemovals([1, 2, 3, 4, 5, 6]) == 0  # strictly increasing
assert sol.minLengthAfterRemovals([1, 1, 1, 1]) == 4  # impossible removals
Test Why
[1,2,3,4] Validates complete pairing
[1,1,2,2,3,3] Checks duplicates with perfect matching
[1000000000,1000000000] Ensures equal values cannot pair
[2,3,4,4,4] Tests odd length with leftover
[5] Smallest input size
[5,5,5] All identical values
[1,2] Smallest removable pair
[2,2] Smallest non-removable pair
[1,1,1,2] Limited pairing opportunities
[1,2,2,2,3] Repeated values in middle
[1,1,1,1,2,2] Dominant frequency edge case
[1,2,3,4,5,6] Fully increasing sequence
[1,1,1,1] No valid removals possible

Edge Cases

All Elements Are Equal

An input like [7,7,7,7] is easy to mishandle if the implementation incorrectly allows equal values to pair. The problem requires strict inequality, nums[i] < nums[j].

The implementation handles this correctly because the comparison uses < rather than <=. Since no comparison succeeds, no pairs are formed and the original length is returned.

Single Element Array

For an input such as [5], there are no two indices available for pairing. A careless implementation might attempt invalid pointer access.

The algorithm safely handles this because the loop condition immediately fails. The function returns 1, which is correct.

Heavy Duplicate Frequency

Consider [1,1,1,1,2]. There is only one larger number available, so only one 1 can pair with 2.

A naive greedy strategy might accidentally overcount possible pairings. The two-pointer approach avoids this by consuming each larger value exactly once. After pairing one 1 with 2, no additional larger values remain, leaving the correct remainder.

Odd-Length Arrays

Arrays with odd lengths, such as [2,3,4,4,4], may leave one unavoidable leftover even after maximum pairing.

The implementation naturally handles this through the formula n - 2 * pairs, which correctly computes the remaining size regardless of parity.