We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reduce Array Size to The Half

Number: 1464

Difficulty: Medium

Paid? No

Companies: Bloomberg, Akuna Capital

Problem Description

Given an integer array, choose a set of integers to remove (i.e., remove all occurrences of each chosen integer) such that at least half of the integers in the original array are removed. Return the minimum size of the set.

Key Insights

  • Count the frequency of each integer in the array.
  • Removing numbers with higher frequencies first minimizes the number of distinct integers needed for removal.
  • Sort the frequencies in descending order and iterate until the cumulative count meets or exceeds half of the original array's size.
  • Use a greedy strategy to decide which numbers to remove.

Space and Time Complexity

Time Complexity: O(n log n) — O(n) to count frequencies and O(n log n) to sort them. Space Complexity: O(n) — for storing the frequency count.

Solution

We use a hash table to count occurrences of every number in the array. After obtaining the frequency of each number, we sort these counts in descending order. Then, we iterate over the sorted frequencies, adding each frequency to a cumulative sum until we reach at least half of the original array length. The number of iterations required gives us the minimum set size. This greedy approach ensures that we are always removing the most frequent elements first to efficiently reduce the array size.

Code Solutions

# Python solution with detailed comments
class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        # Create a frequency map for each number in the array
        freq = {}
        for num in arr:
            freq[num] = freq.get(num, 0) + 1

        # Sort frequency values in descending order
        frequencies = sorted(freq.values(), reverse=True)
        
        removals = 0
        count = 0
        half_size = len(arr) // 2  # Calculate half the size of the array
        
        # Iterate over frequencies and sum them until we've removed at least half of the array
        for f in frequencies:
            removals += f
            count += 1
            if removals >= half_size:
                break
        return count
← Back to All Questions