Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Two Pointers · Binary Search · Greedy
[1,2,3,4]
[1,1,2,2,3,3]
[1000000000,1000000000]
find-the-maximum-number-of-marked-indices)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2856: Minimum Array Length After Pair Removals
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;
}
}
// Accepted solution for LeetCode #2856: Minimum Array Length After Pair Removals
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) }
# Accepted solution for LeetCode #2856: Minimum Array Length After Pair Removals
class Solution:
def minLengthAfterRemovals(self, nums: List[int]) -> int:
cnt = Counter(nums)
pq = [-x for x in cnt.values()]
heapify(pq)
ans = len(nums)
while len(pq) > 1:
x, y = -heappop(pq), -heappop(pq)
x -= 1
y -= 1
if x > 0:
heappush(pq, -x)
if y > 0:
heappush(pq, -y)
ans -= 2
return ans
// Accepted solution for LeetCode #2856: Minimum Array Length After Pair Removals
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2856: Minimum Array Length After Pair Removals
// 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;
// }
// }
// Accepted solution for LeetCode #2856: Minimum Array Length After Pair Removals
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;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair of elements. The outer loop picks one element, the inner loop scans the rest. For n elements that is n × (n−1)/2 comparisons = O(n²). No extra memory — just two loop variables.
Each pointer traverses the array at most once. With two pointers moving inward (or both moving right), the total number of steps is bounded by n. Each comparison is O(1), giving O(n) overall. No auxiliary data structures are needed — just two index variables.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.