Minimum Array Length After Pair Removals solution and explanation
4 more videos on this problem
🔴 2856. Minimum Array Length After Pair Removals II With & Without Priority Queue II Leetcode 2856Aryan Mittal · 17:57 · 3K views
2856. Minimum Array Length After Pair Removals | Leetcode Biweekly 113codingMohan · 21:02 · 1K views
2856. Minimum Array Length After Pair Removals (Leetcode Medium)Programming Live with Larry · 7:40 · 923 views
LeetCode Solution | 2856. Minimum Array Length After Pair Removals | Biweekly Contest 113AlgoArtist · 11:11 · 773 views
【每日一题】LeetCode 2856. Minimum Array Length After Pair RemovalsHuifeng Guan · 7:55 · 462 views
The problem
Given an integer array num sorted in non-decreasing order.
You can perform the following operation any number of times:
- Choose two indices,
iandj, wherenums[i] < nums[j]. - Then, remove the elements at indices
iandjfromnums. 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] <= 109numsis sorted in non-decreasing order.
Approach overview
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.
Approach 1: Two-Pointer Approach
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.
def min_array_length(nums):
n = len(nums)
i = 0
j = 1
while j < n and i < j:
if nums[i] < nums[j]:
i += 1
j += 1
return n - 2 * i
# Example Usage
assert min_array_length([1, 2, 3, 4]) == 0
assert min_array_length([1, 1, 2, 2, 3, 3]) == 0
assert min_array_length([1000000000, 1000000000]) == 2
assert min_array_length([2, 3, 4, 4, 4]) == 1public class MinArrayLength {
public static int minArrayLength(int[] nums) {
int i = 0, j = 1, n = nums.length;
while (j < n && i < j) {
if (nums[i] < nums[j]) {
i++;
}
j++;
}
return n - 2 * i;
}
public static void main(String[] args) {
System.out.println(minArrayLength(new int[]{1, 2, 3, 4})); // Output: 0
System.out.println(minArrayLength(new int[]{1, 1, 2, 2, 3, 3})); // Output: 0
System.out.println(minArrayLength(new int[]{1000000000, 1000000000})); // Output: 2
System.out.println(minArrayLength(new int[]{2, 3, 4, 4, 4})); // Output: 1
}
}#include <vector>
#include <iostream>
int minArrayLength(std::vector<int>& nums) {
int i = 0, j = 1, n = nums.size();
while (j < n && i < j) {
if (nums[i] < nums[j]) {
i++;
}
j++;
}
return n - 2 * i;
}
int main() {
std::vector<int> nums1 = {1, 2, 3, 4};
std::cout << minArrayLength(nums1) << std::endl; // Output: 0
std::vector<int> nums2 = {1, 1, 2, 2, 3, 3};
std::cout << minArrayLength(nums2) << std::endl; // Output: 0
std::vector<int> nums3 = {1000000000, 1000000000};
std::cout << minArrayLength(nums3) << std::endl; // Output: 2
std::vector<int> nums4 = {2, 3, 4, 4, 4};
std::cout << minArrayLength(nums4) << std::endl; // Output: 1
return 0;
}function minArrayLength(nums) {
let i = 0, j = 1;
const n = nums.length;
while (j < n && i < j) {
if (nums[i] < nums[j]) {
i++;
}
j++;
}
return n - 2 * i;
}
console.log(minArrayLength([1, 2, 3, 4])); // Output: 0
console.log(minArrayLength([1, 1, 2, 2, 3, 3])); // Output: 0
console.log(minArrayLength([1000000000, 1000000000])); // Output: 2
console.log(minArrayLength([2, 3, 4, 4, 4])); // Output: 1;using System;
public class Solution {
public int MinArrayLength(int[] nums) {
int i = 0, j = 1, n = nums.Length;
while (j < n && i < j) {
if (nums[i] < nums[j]) {
i++;
}
j++;
}
return n - 2 * i;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MinArrayLength(new int[] {1, 2, 3, 4})); // Output: 0
Console.WriteLine(sol.MinArrayLength(new int[] {1, 1, 2, 2, 3, 3})); // Output: 0
Console.WriteLine(sol.MinArrayLength(new int[] {1000000000, 1000000000})); // Output: 2
Console.WriteLine(sol.MinArrayLength(new int[] {2, 3, 4, 4, 4})); // Output: 1
}
}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.
Time Complexity: O(n), since each element is inspected at most twice.
Space Complexity: O(1), using a constant amount of extra space.
Approach 2: Greedy Matching Approach Using Frequency Count
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.
from collections import Counter
def min_array_length(nums):
freqs = Counter(nums)
unique = sorted(freqs.keys())
pairs = 0
for i in range(len(unique) - 1):
pairs += min(freqs[unique[i]], freqs[unique[i+1]])
return len(nums) - 2 * pairs
# Example Usage
assert min_array_length([1, 2, 3, 4]) == 0
assert min_array_length([1, 1, 2, 2, 3, 3]) == 0
assert min_array_length([1000000000, 1000000000]) == 2
assert min_array_length([2, 3, 4, 4, 4]) == 1import java.util.HashMap;
import java.util.Map;
public class MinArrayLength {
public static int minArrayLength(int[] nums) {
Map<Integer, Integer> freqs = new HashMap<>();
for (int num : nums) {
freqs.put(num, freqs.getOrDefault(num, 0) + 1);
}
int pairs = 0;
int[] unique = freqs.keySet().stream().sorted().mapToInt(Integer::intValue).toArray();
for (int i = 0; i < unique.length - 1; i++) {
pairs += Math.min(freqs.get(unique[i]), freqs.get(unique[i + 1]));
}
return nums.length - 2 * pairs;
}
public static void main(String[] args) {
System.out.println(minArrayLength(new int[]{1, 2, 3, 4})); // Output: 0
System.out.println(minArrayLength(new int[]{1, 1, 2, 2, 3, 3})); // Output: 0
System.out.println(minArrayLength(new int[]{1000000000, 1000000000})); // Output: 2
System.out.println(minArrayLength(new int[]{2, 3, 4, 4, 4})); // Output: 1
}
}#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
int minArrayLength(std::vector<int>& nums) {
std::map<int, int> freqs;
for (int num : nums) {
freqs[num]++;
}
int pairs = 0;
std::vector<int> unique;
for (const auto& entry : freqs) {
unique.push_back(entry.first);
}
for (size_t i = 0; i < unique.size() - 1; i++) {
pairs += std::min(freqs[unique[i]], freqs[unique[i + 1]]);
}
return nums.size() - 2 * pairs;
}
int main() {
std::vector<int> nums1 = {1, 2, 3, 4};
std::cout << minArrayLength(nums1) << std::endl; // Output: 0
std::vector<int> nums2 = {1, 1, 2, 2, 3, 3};
std::cout << minArrayLength(nums2) << std::endl; // Output: 0
std::vector<int> nums3 = {1000000000, 1000000000};
std::cout << minArrayLength(nums3) << std::endl; // Output: 2
std::vector<int> nums4 = {2, 3, 4, 4, 4};
std::cout << minArrayLength(nums4) << std::endl; // Output: 1
return 0;
}function minArrayLength(nums) {
const freqs = {};
nums.forEach(num => { freqs[num] = (freqs[num] || 0) + 1; });
const unique = Object.keys(freqs).map(Number).sort((a, b) => a - b);
let pairs = 0;
for (let i = 0; i < unique.length - 1; i++) {
pairs += Math.min(freqs[unique[i]], freqs[unique[i + 1]]);
}
return nums.length - 2 * pairs;
}
console.log(minArrayLength([1, 2, 3, 4])); // Output: 0
console.log(minArrayLength([1, 1, 2, 2, 3, 3])); // Output: 0
console.log(minArrayLength([1000000000, 1000000000])); // Output: 2
console.log(minArrayLength([2, 3, 4, 4, 4])); // Output: 1;using System;
using System.Collections.Generic;
public class Solution {
public int MinArrayLength(int[] nums) {
var freqs = new Dictionary<int, int>();
foreach (int num in nums) {
if (!freqs.ContainsKey(num)) freqs[num] = 0;
freqs[num]++;
}
int pairs = 0;
var unique = new List<int>(freqs.Keys);
unique.Sort();
for (int i = 0; i < unique.Count - 1; i++) {
pairs += Math.Min(freqs[unique[i]], freqs[unique[i + 1]]);
}
return nums.Length - 2 * pairs;
}
public static void Main() {
var sol = new Solution();
Console.WriteLine(sol.MinArrayLength(new int[] {1, 2, 3, 4})); // Output: 0
Console.WriteLine(sol.MinArrayLength(new int[] {1, 1, 2, 2, 3, 3})); // Output: 0
Console.WriteLine(sol.MinArrayLength(new int[] {1000000000, 1000000000})); // Output: 2
Console.WriteLine(sol.MinArrayLength(new int[] {2, 3, 4, 4, 4})); // Output: 1
}
}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.
Time Complexity: O(n), due to counting frequencies.
Space Complexity: O(k), where k is the number of unique elements.
Approach 3: Greedy + Priority Queue (Max Heap)
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.
function minLengthAfterRemovals(nums: number[]): number {
const cnt: Map<number, number> = new Map();
for (const x of nums) {
cnt.set(x, (cnt.get(x) ?? 0) + 1);
}
const pq = new MaxPriorityQueue<number>();
for (const [_, v] of cnt) {
pq.enqueue(v);
}
let ans = nums.length;
while (pq.size() > 1) {
let x = pq.dequeue();
let y = pq.dequeue();
if (--x > 0) {
pq.enqueue(x);
}
if (--y > 0) {
pq.enqueue(y);
}
ans -= 2;
}
return ans;
}func minLengthAfterRemovals(nums []int) int {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
h := &hp{}
for _, x := range cnt {
h.push(x)
}
ans := len(nums)
for h.Len() > 1 {
x, y := h.pop(), h.pop()
if x > 1 {
h.push(x - 1)
}
if y > 1 {
h.push(y - 1)
}
ans -= 2
}
return ans
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int { return heap.Pop(h).(int) }Complexity comparison
| 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) | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Array Length After Pair Removals easy or hard?
The problem is rated Medium because the greedy insight is not immediately obvious. Many developers initially try simulation or brute force before recognizing that pairing the smallest available element with the earliest valid larger element guarantees the optimal result.
Minimum Array Length After Pair Removals Python/Java solution
Most implementations use a two-pointer loop that scans the array once. The same logic works across Python, Java, C++, C#, and JavaScript because it only requires pointer movement and simple comparisons, producing an O(n) time solution.
How to solve Minimum Array Length After Pair Removals in O(n)?
Use two pointers on the sorted array. Set i at the start and j at the midpoint. When nums[i] < nums[j], form a pair and move both pointers forward; otherwise move j forward. Count valid pairs and compute the remaining length as n - 2 * pairs.
What is the best approach for Minimum Array Length After Pair Removals?
The most efficient approach uses a greedy two-pointer strategy. Since the array is non-decreasing, start one pointer at the beginning and another near the middle. Pair the smallest element with the earliest larger element that satisfies nums[i] < nums[j]. This produces the maximum number of removable pairs in O(n) time and O(1) space.
Is Minimum Array Length After Pair Removals asked at Google/Amazon/Meta?
Greedy pairing and two-pointer problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The problem tests understanding of greedy matching, sorted array traversal, and reasoning about element frequency constraints.
What data structure is used in Minimum Array Length After Pair Removals?
The main techniques rely on arrays and the two-pointer pattern. An alternative solution uses a hash map or counter to track element frequencies and reason about the most frequent value limiting the number of valid pair removals.
What is the time complexity of Minimum Array Length After Pair Removals?
The optimal solution runs in O(n) time because each element is processed at most once using two pointers. The space complexity is O(1) when using the pointer-based greedy approach. A frequency-count implementation also runs in O(n) time but uses O(n) additional space.