Minimum Array Length After Pair Removals - Practice Coding Problems

Minimum Array Length After Pair Removals - Problem

Given an integer array nums 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.

Input & Output

Example 1 — Balanced Distribution

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

› Output: 0

💡 Note: We can pair (1,3), (1,3), leaving element 2. Then pair another available element with 2. All elements can be paired, so minimum length is 0.

Example 2 — Dominant Element

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

› Output: 1

💡 Note: Element 1 appears 3 times, others appear 1-2 times. We can pair each 1 with different elements: (1,2), (1,3), (1,3). One element 1 remains unpaired.

Example 3 — All Same Elements

$ Input: nums = [1,1,1,1]

› Output: 4

💡 Note: All elements are the same (1). Since we need nums[i] < nums[j] to form a pair, no pairs can be formed. All 4 elements remain.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁶ ≤ nums[i] ≤ 10⁶
nums is sorted in non-decreasing order

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array with element frequencies

Pairing Strategy

Most frequent element limits total pairs

Mathematical Result

Formula gives minimum remaining length

Key Takeaway

🎯 Key Insight: The most frequent element determines how many elements will remain unpaired, leading to a simple mathematical formula.

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is that the minimum remaining length depends only on the most frequent element. Since we can only pair elements where nums[i] < nums[j], identical elements cannot be paired with each other. The optimal strategy is to pair the most frequent element with all different elements. If the most frequent element appears more than half the time, some instances will remain unpaired. Best approach uses frequency counting with formula max(0, 2×maxFreq - n). Time: O(n), Space: O(k) where k is number of unique elements.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count Analysis	O(n)	O(n)	Count element frequencies and calculate pairs mathematically
Greedy Optimal Pairing	O(n)	O(k)	Use mathematical insight that answer depends only on maximum frequency
Brute Force Simulation	O(n³)	O(1)	Repeatedly find and remove valid pairs until no more pairs can be formed

Frequency Count Analysis — Algorithm Steps

Step 1: Count frequency of each unique element
Step 2: Find the maximum frequency among all elements
Step 3: Return max(0, 2 * maxFreq - n) where n is array length

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count occurrences of each element

Find Max Frequency

The most frequent element limits pairing

Calculate Result

Formula: max(0, 2*maxFreq - n)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    
    // Simple frequency counting using arrays
    // Assuming values are in reasonable range
    int freq[20001] = {0}; // Support range -10000 to 10000
    int offset = 10000;
    
    for (int i = 0; i < numsSize; i++) {
        freq[nums[i] + offset]++;
    }
    
    // Find maximum frequency
    int maxFreq = 0;
    for (int i = 0; i < 20001; i++) {
        if (freq[i] > maxFreq) {
            maxFreq = freq[i];
        }
    }
    
    // The answer is max(0, 2 * max_freq - numsSize)
    int result = 2 * maxFreq - numsSize;
    return result > 0 ? result : 0;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON array parsing
    int nums[1000];
    int size = 0;
    char* ptr = line + 1; // Skip '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '-' || (*ptr >= '0' && *ptr <= '9')) {
            nums[size++] = strtol(ptr, &ptr, 10);
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies, then find maximum

✓ Linear Growth

Space Complexity

O(n)

Hash map stores frequency for each unique element

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler