Reduce Array Size to The Half

Medium
344.

Reduce Array Size to The Half

Reduce Array Size to The Half is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Microsoft interviews.

You are given an integer array arr. Choose a set of integers and remove every occurrence of them from arr.

Return the minimum size of such a set so that at least half of the array's elements are removed.

Example 1

Input
arr = [3,3,3,3,5,5,5,2,2,7]
Output
2
Explanation
Removing {3,7} leaves 5 of the 10 elements.

Example 2

Input
arr = [7,7,7,7,7,7]
Output
1

Example 3

Input
arr = [1,2]
Output
1

Constraints

  • 2 <= arr.length <= 40
  • arr.length is even.
  • 1 <= arr[i] <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var minSetSize = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Reduce Array Size to The Half — Problem & Solution

Reduce Array Size to The Half solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Reduce Array Size to The Half is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Microsoft interviews.

Problem statement

You are given an integer array arr. Choose a set of integers and remove every occurrence of them from arr.

Return the minimum size of such a set so that at least half of the array's elements are removed.

Example 1

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Removing {3,7} leaves 5 of the 10 elements.

Example 2

Input: arr = [7,7,7,7,7,7]
Output: 1

Example 3

Input: arr = [1,2]
Output: 1

Constraints

  • 2 <= arr.length <= 40
  • arr.length is even.
  • 1 <= arr[i] <= 100000

Hints for Reduce Array Size to The Half

  1. Hint 1

    Removing a value removes all of its copies at once, so only the frequencies matter.

  2. Hint 2

    Take the most frequent values first — each choice removes as much as possible.

  3. Hint 3

    Sort the frequencies descending and accumulate until the running total reaches half the length.

How to solve Reduce Array Size to The Half

Removing a value removes all its copies, so sort the frequencies descending and take the largest until at least half the array is gone.

Approach

  1. Count frequencies.
  2. Sort them descending and accumulate; stop when the total reaches n / 2.
  3. Return how many were taken.

Why it works

Each chosen value removes its full frequency; to reach the threshold with the fewest choices, take the largest frequencies first (exchange argument).

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • n is even by the constraints, so n // 2 is exact.

Reference solution

Python

def minSetSize(arr) -> int:
    count = {}
    for x in arr:
        count[x] = count.get(x, 0) + 1
    freqs = sorted(count.values(), reverse=True)
    removed = chosen = 0
    half = len(arr) // 2
    for f in freqs:
        removed += f
        chosen += 1
        if removed >= half:
            break
    return chosen

Java

public static int minSetSize(int[] arr) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : arr) count.put(x, count.getOrDefault(x, 0) + 1);
    List<Integer> freqs = new ArrayList<>(count.values());
    Collections.sort(freqs, Collections.reverseOrder());
    int removed = 0, chosen = 0;
    int half = arr.length / 2;
    for (int f : freqs) {
        removed += f;
        chosen++;
        if (removed >= half) break;
    }
    return chosen;
}

C++

int minSetSize(vector<int>& arr) {
    unordered_map<int, int> count;
    for (int x : arr) count[x]++;
    vector<int> freqs;
    for (const auto& kv : count) freqs.push_back(kv.second);
    sort(freqs.begin(), freqs.end(), greater<int>());
    int removed = 0, chosen = 0;
    int half = (int) arr.size() / 2;
    for (int f : freqs) {
        removed += f;
        chosen++;
        if (removed >= half) break;
    }
    return chosen;
}

JavaScript

var minSetSize = function(arr) {
    const count = new Map();
    for (let i = 0; i < arr.length; i++) {
        count.set(arr[i], (count.get(arr[i]) || 0) + 1);
    }
    const freqs = [];
    count.forEach(function(c) { freqs.push(c); });
    freqs.sort(function(a, b) { return b - a; });
    let removed = 0, chosen = 0;
    const half = arr.length / 2;
    for (let i = 0; i < freqs.length; i++) {
        removed += freqs[i];
        chosen++;
        if (removed >= half) break;
    }
    return chosen;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets