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

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

✓ Memoization

⏱️ Time: N/A Space: N/A

Brute Force - Try All Combinations

⏱️ Time: O(C(n,k) × n) Space: O(n)

Try every possible combination of removing k elements from the array. For each combination, count the remaining unique integers and track the minimum. This exhaustive approach guarantees the correct answer but is extremely slow.

Frequency Count + Greedy Removal

⏱️ Time: O(n log n) Space: O(n)

Count the frequency of each unique integer, then sort these frequencies. Greedily remove entire groups starting with the lowest frequency until we've removed k elements total.

Min Heap Approach

⏱️ Time: O(n + m log m) Space: O(n)

Count frequencies and use a min heap to efficiently get the smallest frequencies. This avoids sorting and can be more efficient for partial processing of frequencies.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* arr, int n, int k) {
    if (n == 0) return 0;
    
    // Sort array to count frequencies
    qsort(arr, n, sizeof(int), compare);
    
    // Count frequencies
    int frequencies[n];
    int freqCount = 0;
    int currentNum = arr[0];
    int currentFreq = 1;
    
    for (int i = 1; i < n; i++) {
        if (arr[i] == currentNum) {
            currentFreq++;
        } else {
            frequencies[freqCount++] = currentFreq;
            currentNum = arr[i];
            currentFreq = 1;
        }
    }
    frequencies[freqCount++] = currentFreq;
    
    // Sort frequencies
    qsort(frequencies, freqCount, sizeof(int), compare);
    
    // Remove elements starting from lowest frequencies
    int remaining = k;
    int uniqueCount = freqCount;
    
    for (int i = 0; i < freqCount; i++) {
        if (remaining >= frequencies[i]) {
            remaining -= frequencies[i];
            uniqueCount--;
        } else {
            break;
        }
    }
    
    return uniqueCount;
}

int* parseArray(char* input, int* n) {
    *n = 0;
    if (strcmp(input, "[]") == 0) {
        return NULL;
    }
    
    // Count numbers
    int count = 1;
    for (int i = 0; input[i]; i++) {
        if (input[i] == ',') count++;
    }
    
    int* arr = (int*)malloc(count * sizeof(int));
    *n = count;
    
    // Parse numbers
    char* ptr = input + 1; // Skip '['
    for (int i = 0; i < count; i++) {
        arr[i] = strtol(ptr, &ptr, 10);
        while (*ptr && (*ptr == ',' || *ptr == ' ')) ptr++;
    }
    
    return arr;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int n;
    int* arr = parseArray(line, &n);
    
    fgets(line, sizeof(line), stdin);
    int k = atoi(line);
    
    if (arr == NULL) {
        printf("0\n");
        return 0;
    }
    
    printf("%d\n", solution(arr, n, k));
    
    free(arr);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚡ Linearithmic

Space Complexity

⚡ 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