Reduce Array Size to The Half - Practice Coding Problems

Reduce Array Size to The Half - Problem

Array Hash Table Greedy Sorting Heap (Priority Queue) Medium

You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

Input & Output

Example 1 — Basic Case

$ Input: arr = [3,3,3,3,5,5,9,2,8]

› Output: 2

💡 Note: We can remove all occurrences of 3 (removes 4 elements) and all occurrences of 5 (removes 2 elements). Total removed: 6 elements ≥ 4 (half of 9). Minimum set size is 2.

Example 2 — Single Element Dominates

$ Input: arr = [7,7,7,7,7,7]

› Output: 1

💡 Note: Remove all occurrences of 7, which removes all 6 elements ≥ 3 (half of 6). Only need 1 element in set.

Example 3 — All Elements Unique

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

› Output: 2

💡 Note: All elements appear once. Need to remove ≥ 2 elements (half of 4). Must pick any 2 elements, so minimum set size is 2.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

[3,3,3,3,5,5,9,2,8] - need to remove ≥ 4 elements

Count & Sort

Frequencies: 3→4, 5→2, others→1 each

Greedy Selection

Pick {3,5} removes 6 elements, set size = 2

Key Takeaway

🎯 Key Insight: Always remove the most frequent elements first to minimize the set size needed

Asked in

f Facebook 45 a Amazon 38 G Google 32 M Microsoft 28

The key insight is to greedily remove the most frequent elements first. Count frequencies, sort by frequency descending, then pick elements until at least half the array is removed. Best approach is Frequency Count + Greedy with Time: O(n log k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^k × n)	O(k)	Generate all possible sets and check which minimum set removes at least half elements
Max Heap Approach	O(n log k)	O(k)	Use max heap to efficiently get most frequent elements in order
Frequency Count + Greedy	O(n log k)	O(k)	Count frequencies, sort by frequency descending, greedily pick most frequent

Brute Force - Try All Combinations — Algorithm Steps

Find all unique values in array
Generate all possible subsets of unique values
For each subset, count total elements removed
Return minimum subset size that removes ≥ half

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Build frequency map of all elements

Generate Subsets

Try all combinations of unique values

Check Removal

Find minimum subset removing ≥ half elements

Code -

solution.c — C

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

#define MAX_SIZE 1000

typedef struct {
    int val;
    int freq;
} FreqPair;

int canRemoveHalf(FreqPair* pairs, int n, int target, int size, int start, int count, int removed) {
    if (count == size) return removed >= target;
    if (start >= n) return 0;
    
    // Include current
    if (canRemoveHalf(pairs, n, target, size, start + 1, count + 1, removed + pairs[start].freq)) {
        return 1;
    }
    
    // Exclude current
    return canRemoveHalf(pairs, n, target, size, start + 1, count, removed);
}

int solution(int* arr, int arrSize) {
    FreqPair pairs[MAX_SIZE];
    int uniqueCount = 0;
    
    // Count frequencies
    for (int i = 0; i < arrSize; i++) {
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (pairs[j].val == arr[i]) {
                pairs[j].freq++;
                found = 1;
                break;
            }
        }
        if (!found) {
            pairs[uniqueCount].val = arr[i];
            pairs[uniqueCount].freq = 1;
            uniqueCount++;
        }
    }
    
    int target = arrSize / 2;
    
    for (int size = 1; size <= uniqueCount; size++) {
        if (canRemoveHalf(pairs, uniqueCount, target, size, 0, 0, 0)) {
            return size;
        }
    }
    
    return uniqueCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[MAX_SIZE];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL && size < MAX_SIZE) {
        if (strlen(token) > 0) {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(arr, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^k × n)

Generate 2^k subsets where k is unique elements, check each subset in O(n) time

✓ Linear Growth

Space Complexity

O(k)

Store frequency map of k unique elements

✓ Linear Space

156.0K Views

Medium Frequency

~15 min Avg. Time

2.8K 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