algoadvance

Leetcode 347. Top K Frequent Elements

Problem Statement

Given a non-empty array of integers, you need to return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

Clarifying Questions

  1. Can the input array be empty?
    • No, the problem states that the array will be non-empty.
  2. Can there be negative numbers in the array?
    • Yes, the problem does not restrict the type of integers, so negative numbers are allowed.
  3. Should the result be in any specific order?
    • The order of elements in the result does not matter.

Strategy

  1. Frequency Mapping:
    • First, count the frequency of each element using a hash map (unordered_map).
  2. Bucket Sort:
    • Since we want to find the most frequent elements, we can use a bucket sort. Create an array of buckets where the index represents the frequency and each bucket contains the list of numbers with that frequency.
  3. Collect Results:
    • Start from the highest possible frequency and collect elements until we’ve gathered k elements.

This approach guarantees that we can handle the required time complexity better than O(n log n).

Code

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // Step 1: Count the frequency of each element
        unordered_map<int, int> frequencyMap;
        for (int num : nums) {
            frequencyMap[num]++;
        }
        
        // Step 2: Create buckets where index represents frequency
        int n = nums.size();
        vector<vector<int>> buckets(n + 1);
        for (auto& pair : frequencyMap) {
            int frequency = pair.second;
            int number = pair.first;
            buckets[frequency].push_back(number);
        }

        // Step 3: Collect the top k frequent elements
        vector<int> result;
        for (int i = n; i >= 0 && result.size() < k; --i) {
            if (!buckets[i].empty()) {
                for (int num : buckets[i]) {
                    result.push_back(num);
                    if (result.size() == k) {
                        return result;
                    }
                }
            }
        }
        
        return result;
    }
};

Time Complexity

  1. Frequency Map Construction:
    • This takes O(n) time to count the frequency of each element.
  2. Bucket Sort:
    • Creating and populating the buckets takes O(n) time.
  3. Collect Results:
    • Collecting top k elements takes O(n) time in the worst case where all elements are unique and we might have to look in every bucket.

Overall, the time complexity is O(n), which is efficient given the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI