Maximum Distinct Elements (Maximize Distinct Values After K Removals)

• Maximum Distinct Elements is a greedy Top K Elements problem.
• Numbers with frequency exactly one are already distinct and cost nothing.
• For numbers with frequency greater than one, the cost to make them distinct is count - 1 removals.
• A min-heap of surplus counts lets you clear the cheapest duplicates first.
• After all duplicates are cleared, any remaining budget removes distinct elements, decreasing the count.
• Time is O(N + D log D) and space is O(D) where D is the number of distinct values.

What is the Maximum Distinct Elements problem?

Given an array of numbers and a removal budget K, find the maximum number of distinct elements that can remain after removing at most K elements. The goal is to spend removals wisely: first eliminate duplicates to create more distinct values, and avoid removing elements that are already unique.

How does the frequency count work?

The first step is to count the frequency of each number. Numbers with frequency 1 are already distinct and need no removals. Numbers with frequency greater than 1 have surplus copies that must be removed to make them distinct.

package com.bank.service;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class MaxDistinctService {

    /**
     * Maximizes distinct merchant categories after K removals.
     * Used by the National Bank of India compliance team.
     */
    public static int maxDistinct(int[] categories, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int cat : categories) {
            freq.merge(cat, 1, Integer::sum);
        }

        int distinct = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int count : freq.values()) {
            if (count == 1) {
                distinct++; // Already unique, no cost
            } else {
                minHeap.offer(count); // Needs count-1 removals
            }
        }

        // Phase 1: Spend budget clearing smallest surpluses
        while (!minHeap.isEmpty() && k > 0) {
            int count = minHeap.poll();
            int needed = count - 1;
            if (k >= needed) {
                k -= needed;
                distinct++; // Successfully made distinct
            }
            // If k < needed, cannot fully clear this one
        }

        // Phase 2: Remaining budget removes distinct elements
        distinct -= k; // Each remaining removal kills one distinct
        return Math.max(0, distinct);
    }

    public static void main(String[] args) {
        int[] categories = {1, 2, 3, 3, 3, 4, 4, 5};
        int k = 3;
        System.out.println("Max distinct after " + k + " removals: "
            + maxDistinct(categories, k));
    }
}

javac -d out com/bank/service/MaxDistinctService.java
java -cp out com.bank.service.MaxDistinctService

Max distinct after 3 removals: 5

Why does the greedy approach work?

Spending removals on the smallest surplus counts first maximizes how many numbers we can fully reduce to a single copy. A number with frequency 2 needs only 1 removal to become distinct, while a number with frequency 5 needs 4 removals. By processing the cheapest conversions first, we convert the most numbers within our budget.

This is a classic greedy argument: per unit of budget spent, clearing a smaller surplus produces a higher return (one new distinct element for fewer removals).

What happens when budget remains after clearing all duplicates?

If after clearing all duplicates we still have removals left, each additional removal must target an element that is already appearing exactly once. Each such removal destroys one distinct element. So we subtract the remaining budget from the distinct count.

// After phase 1: all duplicates cleared, k = 2 remaining
// We have 7 distinct elements, but must remove 2 more
// distinct -= 2 -> 5 distinct elements

What are the edge cases?

Several edge cases deserve attention.

• K is zero: no removals allowed, distinct count is just the number of unique values.
• K >= array length: can remove everything, result is 0.
• All elements identical: one distinct value, need count-1 removals to keep it.
• All elements already distinct: no duplicates to clear, budget removes distinct elements.

package com.bank.core;

public class MaxDistinctEdgeCases {
    public static void main(String[] args) {
        // All identical
        System.out.println(maxDistinct(new int[]{5, 5, 5, 5}, 2)); // 1

        // All distinct, budget removes some
        System.out.println(maxDistinct(new int[]{1, 2, 3, 4}, 2)); // 2

        // K is zero
        System.out.println(maxDistinct(new int[]{1, 1, 2, 3}, 0)); // 3
    }

    static int maxDistinct(int[] arr, int k) {
        java.util.Map<Integer, Integer> freq = new java.util.HashMap<>();
        for (int n : arr) freq.merge(n, 1, Integer::sum);
        int distinct = 0;
        java.util.PriorityQueue<Integer> heap = new java.util.PriorityQueue<>();
        for (int c : freq.values()) { if (c == 1) distinct++; else heap.offer(c); }
        while (!heap.isEmpty() && k > 0) {
            int c = heap.poll(); int need = c - 1;
            if (k >= need) { k -= need; distinct++; }
        }
        distinct -= k;
        return Math.max(0, distinct);
    }
}

1
2
3

What is the time and space complexity?

Counting frequencies takes O(N) time. Building the heap with D distinct values takes O(D log D). Processing the heap takes O(D log D) in the worst case. Total time is O(N + D log D). Space is O(D) for the frequency map and heap.

Since D <= N, the worst case is O(N log N), but in practice D is often much smaller than N when there are many duplicates.

How is this different from Top K Frequent Elements?

| Aspect | Maximum Distinct Elements | Top K Frequent Elements |
|---|---|---|
| Goal | Maximize distinct count after removals | Find K most frequent elements |
| Heap usage | Min-heap of surplus counts | Min-heap of frequencies |
| Budget | K removals to spend | No budget concept |
| Strategy | Clear cheapest duplicates first | Keep highest frequencies |

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• Two-phase structure: the algorithm has two distinct phases: spending budget to increase distinct count, then potentially losing distinct count. Many candidates miss the second phase.
• Sorting alternative: instead of a heap, sort the surplus counts and iterate. This is simpler and has the same time complexity.
• Greedy proof: the exchange argument shows that any other ordering of removals either matches or underperforms the smallest-first strategy.

What are common interview follow-up questions?

Interviewers often extend this problem.

• Minimize distinct elements: the opposite goal, remove elements to minimize distinct count. Here you remove the rarest elements first.
• K additions instead of removals: add up to K elements to maximize or minimize distinct count.
• Maximum distinct in a sliding window: combine with sliding window techniques.