Least Number of Unique Integers after K Removals

Least Number of Unique Integers after K Removals - Problem

Given an array of integers arr and an integer k, find the least number of unique integers after removing exactly k elements.

You need to remove exactly k elements from the array, and your goal is to minimize the number of distinct integers that remain.

Strategy: To minimize unique integers, remove elements with the lowest frequencies first, as this eliminates entire unique values faster than removing high-frequency elements.

Input & Output

Example 1 — Basic Case

$ Input: arr = [4,3,1,1,3], k = 2

› Output: 2

💡 Note: Count frequencies: 4 appears 1 time, 3 appears 2 times, 1 appears 2 times. Remove the element with frequency 1 (value 4) using 1 removal. We have 1 more removal left but can't eliminate any complete group. Result: 2 unique values remain (3 and 1).

Example 2 — Complete Elimination

$ Input: arr = [5,5,4], k = 2

› Output: 1

💡 Note: Count frequencies: 5 appears 2 times, 4 appears 1 time. Remove value 4 (1 removal), then remove one instance of 5 (1 more removal). We used 2 removals total. Result: 1 unique value remains (5).

Example 3 — Minimum Input

$ Input: arr = [1], k = 1

› Output: 0

💡 Note: Only one element exists with frequency 1. Remove it completely using 1 removal. Result: 0 unique values remain.

Constraints

1 ≤ arr.length ≤ 10⁵
1 ≤ arr[i] ≤ 10⁹
1 ≤ k ≤ arr.length

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [4,3,1,1,3] with k=2 removals needed

Frequency Strategy

Count frequencies and remove rarest elements first

Optimal Result

Remove value 4 completely → 2 unique values remain

Key Takeaway

🎯 Key Insight: Always remove the rarest elements first - this eliminates entire unique values faster than removing common elements partially

Asked in

a Amazon 15 f Facebook 8 G Google 6

The key insight is to use frequency counting and greedy removal - always eliminate rare elements first to minimize unique count. Count frequencies of each element, sort them, then greedily remove complete groups starting from lowest frequency. Best approach uses frequency counting + sorting: Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(C(n,k) × n)	O(n)	Generate all possible ways to remove k elements and find minimum unique count
Min Heap Approach	O(n + m log m)	O(n)	Use min heap to efficiently extract elements with lowest frequencies
Frequency Count + Greedy Removal	O(n log n)	O(n)	Count frequencies, then greedily remove elements with lowest frequency first

Brute Force - Try All Combinations — Algorithm Steps

Generate all C(n,k) combinations of k elements to remove
For each combination, count unique integers in remaining elements
Return minimum unique count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all C(n,k) ways to remove k elements

Test Each

Count unique integers in each remaining set

Find Minimum

Return the smallest unique count found

Code -

solution.c — C

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

int solution(int* arr, int arrSize, int k) {
    // For simplicity in C, we'll implement a limited brute force
    // This is not practical for real use due to complexity
    int minUnique = INT_MAX;
    
    // Simple approach: try removing first k elements, last k elements, etc.
    // Full combination generation is too complex for this example
    for (int start = 0; start <= arrSize - k; start++) {
        int unique[1000] = {0}; // Assuming values are small for this demo
        int uniqueCount = 0;
        
        for (int i = 0; i < arrSize; i++) {
            if (i < start || i >= start + k) {
                // This element remains
                int val = arr[i] + 500; // Offset for negative values
                if (val >= 0 && val < 1000 && unique[val] == 0) {
                    unique[val] = 1;
                    uniqueCount++;
                }
            }
        }
        
        if (uniqueCount < minUnique) {
            minUnique = uniqueCount;
        }
    }
    
    return minUnique;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[100];
    int arrSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL && arrSize < 100) {
        arr[arrSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(arr, arrSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(C(n,k) × n)

C(n,k) combinations times O(n) to count unique elements per combination

✓ Linear Growth

Space Complexity

O(n)

Space to store each combination and count frequencies

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~15 min Avg. Time

856 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

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler