Scale Engineer

Minimum Array Length After Pair Removals

Med
#2553Time: O(n), where n is the number of elements in the array. Both pointers `i` and `j` traverse their respective halves of the array at most once.Space: O(1) extra space, as we only use a few variables for the pointers and the count.1 company
Patterns
Two PointersGreedyCounting
Algorithms
Binary Search
Data structures
ArrayHash Table
Companies
Snowflake

Prompt

Given an integer array num sorted in non-decreasing order.

You can perform the following operation any number of times:

  • Choose two indices, i and j, where nums[i] < nums[j].
  • Then, remove the elements at indices i and j from nums. The remaining elements retain their original order, and the array is re-indexed.

Return the minimum length of nums after applying the operation zero or more times.

 

Example 1:

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

Output: 0

Explanation:

Example 2:

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

Output: 0

Explanation:

Example 3:

Input: nums = [1000000000,1000000000]

Output: 2

Explanation:

Since both numbers are equal, they cannot be removed.

Example 4:

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

Output: 1

Explanation:

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • nums is sorted in non-decreasing order.

Approaches

2 approaches with complexity analysis and trade-offs.

The core idea is that to maximize the number of removals, we should pair smaller elements with larger elements. Since the input array nums is sorted, this naturally suggests pairing elements from the first half of the array with elements from the second half. This greedy strategy can be implemented efficiently using a two-pointer technique.

Algorithm

  • Initialize two pointers, i starting at 0 and j starting at (n + 1) / 2, where n is the length of the array.
  • Initialize a counter pairs to 0.
  • Loop while i is in the first half (i.e., i < (n + 1) / 2) and j is in the second half (i.e., j < n):
    • If nums[i] < nums[j], it means we can form a pair. Increment pairs, and advance both pointers i and j.
    • Otherwise (nums[i] >= nums[j]), we cannot pair nums[i] with nums[j]. We need to find a larger element in the second half for nums[i], so we only advance j.
  • After the loop terminates, the total number of elements removed is 2 * pairs.
  • The minimum length of the remaining array is n - 2 * pairs.

Walkthrough

We use two pointers, i and j, to traverse the first and second halves of the array, respectively. The pointer i starts at the beginning of the array (0), and j starts at the beginning of the second half (at index (n + 1) / 2 to handle both even and odd length arrays correctly). We iterate through the array and try to form pairs. If nums[i] is smaller than nums[j], we have a valid pair. We count this pair and advance both pointers to look for the next pair. If nums[i] is not smaller than nums[j], we can't pair them. Since nums[i] is fixed, we need to find a larger element in the second half, so we advance j while keeping i the same. The process continues until one of the pointers goes out of its respective half's bounds. The final answer is the initial length minus twice the number of pairs found.

class Solution {    public int minLengthAfterRemovals(List<Integer> nums) {        int n = nums.size();        if (n == 0) {            return 0;        }         int i = 0;        int j = (n + 1) / 2;        int pairs = 0;         while (i < n / 2 && j < n) {            if (nums.get(i) < nums.get(j)) {                pairs++;                i++;                j++;            } else {                j++;            }        }         return n - 2 * pairs;    }}

Complexity

Time

O(n), where n is the number of elements in the array. Both pointers `i` and `j` traverse their respective halves of the array at most once.

Space

O(1) extra space, as we only use a few variables for the pointers and the count.

Trade-offs

Pros

  • Achieves optimal time and space complexity.

  • The logic is a direct and intuitive simulation of an effective pairing strategy.

  • Works correctly for both even and odd length arrays due to the (n+1)/2 split point.

Cons

  • The optimality of this specific greedy strategy (pairing the first half with the second half) might not be immediately obvious without some reasoning.

Solutions

class Solution {public  int minLengthAfterRemovals(List<Integer> nums) {    Map<Integer, Integer> cnt = new HashMap<>();    for (int x : nums) {      cnt.merge(x, 1, Integer : : sum);    }    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());    for (int x : cnt.values()) {      pq.offer(x);    }    int ans = nums.size();    while (pq.size() > 1) {      int x = pq.poll();      int y = pq.poll();      x--;      y--;      if (x > 0) {        pq.offer(x);      }      if (y > 0) {        pq.offer(y);      }      ans -= 2;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem