Given an integer array num sorted in non-decreasing order.
You can perform the following operation any number of times:
i and j, where nums[i] < nums[j].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 <= 1051 <= nums[i] <= 109nums is sorted in non-decreasing order.Problem Overview: You are given a non‑decreasing array. In one operation, pick two indices i < j where nums[i] < nums[j] and remove both elements. The goal is to perform operations so the remaining array length is as small as possible.
Approach 1: Two-Pointer Greedy Pairing (O(n) time, O(1) space)
The array is already sorted, which makes pairing straightforward. Split the array conceptually into two halves. Use two pointers: i starting at the beginning (smaller values) and j starting around the middle (potential larger partners). If nums[i] < nums[j], you can form a valid pair, so increment both pointers and count the pair. If not, move j forward to find a larger element. This greedy pairing works because matching the smallest available element with the earliest valid larger element preserves larger values for future matches. After scanning once, the remaining length is n - 2 * pairs. The algorithm runs in linear time and constant space, making it ideal for large inputs and a common pattern in two pointers problems on sorted arrays.
Approach 2: Greedy Matching Using Frequency Count (O(n) time, O(n) space)
This approach focuses on value frequencies rather than indices. Count how often each number appears using a frequency map or counter from hash table utilities. The limiting factor is the most frequent element. If one value appears more than half the array (maxFreq > n/2), those extra elements cannot all be paired with distinct larger values. The leftover length becomes 2 * maxFreq - n. Otherwise, elements can mostly cancel each other out and the remaining length is simply n % 2. This reasoning comes from the observation that every valid operation removes two different values, so the most frequent value determines how many unmatched elements remain. The approach uses counting and greedy reasoning often seen in greedy and frequency‑based array problems.
Recommended for interviews: The two‑pointer greedy approach is usually the expected solution because it directly uses the sorted property and runs in O(n) time with O(1) extra space. The frequency insight is also valuable because it reveals the mathematical structure of the problem. Demonstrating both shows strong understanding: the pointer solution proves implementation skill, while the counting observation shows deeper algorithmic reasoning.
The strategy here is to use two pointers to attempt pair removals. The two pointers can start at the beginning of the array. The first pointer advances steadily, while the second pointer moves forward only when a valid pair has been found.
By iterating through the list and attempting to pair each element with the next possible greater element (using properties of a sorted list), we can simulate removing pairs and maintain the array indices efficiently as we examine possible pairs. Utilizing this method ensures that minimal computational resources are spent checking conditions for each potential pair, delivering an optimal solution.
This function iterates over the sorted list using two pointers. The first pointer, i, moves only when a valid pair is found; the second pointer, j, continuously increments. We count valid pairs (i) and subtract twice this number from the total length to determine the minimal length after possible removals.
Python
Java
C++
C#
JavaScript
Time Complexity: O(n), since each element is inspected at most twice.
Space Complexity: O(1), using a constant amount of extra space.
This method relies on using a frequency count to manage pairs. By scanning the list, we can ascertain the number of pairable elements using the minimum frequency count of smaller and larger numbers.
The frequency of each unique number in the sorted list will guide the number of possible pairs. By pairing the minimum frequency of any two successive numbers, we can calculate how many elements can be removed optimally, leading to a reduced final length of the array.
This solution calculates a frequency distribution for the array using collections.Counter. It iterates over each distinct pair of numbers with their frequencies, forming as many pairs as possible and counting the total to inform the result.
Python
Java
C++
C#
JavaScript
Time Complexity: O(n), due to counting frequencies.
Space Complexity: O(k), where k is the number of unique elements.
We use a hash table cnt to count the occurrence of each element in the array nums, then add each value in cnt to a priority queue (max heap) pq. Each time we take out two elements x and y from pq, decrease their values by one. If the value after decrement is still greater than 0, we add the decremented value back to pq. Each time we take out two elements from pq, it means we delete a pair of numbers from the array, so the length of the array decreases by 2. When the size of pq is less than 2, we stop the deletion operation.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | Time Complexity: O(n), since each element is inspected at most twice. |
| Greedy Matching Approach Using Frequency Count | Time Complexity: O(n), due to counting frequencies. |
| Greedy + Priority Queue (Max Heap) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Greedy Pairing | O(n) | O(1) | Best when the array is already sorted or guaranteed non-decreasing |
| Greedy Frequency Count | O(n) | O(n) | Useful when reasoning about value distribution or when implementing via counters |
🔴 2856. Minimum Array Length After Pair Removals II With & Without Priority Queue II Leetcode 2856 • Aryan Mittal • 3,060 views views
Watch 5 more video solutions →Practice Minimum Array Length After Pair Removals with our built-in code editor and test cases.
Practice on FleetCode