Published 2024-12-28

0347. Top K Frequent Elements

leetcode

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may assume that the answer is unique, and you may return the answer in any order.

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

Solution Description

To implement the solution to this problem, we need to follow these steps:

  • First, count the frequency of each element in the array; this can be efficiently done using a JavaScript Map or Object.
  • Create an array of numbers frequency entries, which will store numbers of similar frequency together.
  • Iterate over the frequency count and populate the frequency array.
  • Make use of a heap (priority queue) that enables us to keep track of the top k elements with greatest frequency efficiently.
  • Use this heap to determine the k most frequent elements, and return them as a result.
  • Time Complexity: O(N log k), where N is the number of elements in nums. We iterate nums once to populate the frequency map, then we perform k operations.
  • Space Complexity: O(N), storing frequency counts and heap of k elements.

Example

Consider nums = [1,1,1,2,2,3] and k=2.

  • Count frequencies: 1: 3, 2: 2, 3: 1
  • Use the bucket sort principle to arrange based on occurrence frequency.
  • Select the top k=2 elements from the most frequent to least in the list: they are 1 and 2.

References

Solution

My custom tests are failing, but the solution was accepted. I have failed to implement my own MaxQueue. So painful ;)

2024-12-30 Top K Frequent Elements - LeetCode leetcode.com 

/**
 * Main function to find the top k frequent elements.
 * @param {number[]} nums - An array of integers.
 * @param {number} k - Number of top elements to return.
 * @return {number[]} Top k frequent elements.
 */
function topKFrequent(nums, k) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    log(`Input nums: ${nums}, k: ${k}`);

    // build num frequency histogram
    const freq = {};

    for (const el of nums) {
        freq[el] = el in freq ? freq[el] + 1 : 1;
    }

    log('frequency map:')
    table(freq);

    // push to the heap

    const freqValueIndex = 1;
    const freqKeyIndex = 0;


    const unsorted = [];

    for (const freqKey of Object.keys(freq)) {
        const item = [Number(freqKey), freq[freqKey]];
        unsorted.push(item);
    }

    log(`unsorted = `);
    table(unsorted);

    const sorted = unsorted.sort((pairA, pairB) => pairB[freqValueIndex] - pairA[freqValueIndex]);

    log(`sorted = `);
    table(sorted);

    const result = [];

    for (let i = 0; i < k; i++) {
        const item = sorted.shift();
        if (item) {
            result.push(item[freqKeyIndex]);
        } else {
            break;
        }
    }

    log(`result = ${result}`);

    return result;
}

// Test cases to verify the solution
const testCases = [
    { nums: [6,0,1,4,9,7,-3,1,-4,-8,4,-7,-3,3,2,-3,9,5,-4,0], k: 2, expected: [-3,0,1,4,9,-4] },
    { nums: [1,1,1,2,2,3], k: 2, expected: [1, 2] },
    { nums: [1], k: 1, expected: [1] },
    { nums: [1,2,3,1,2,4,4,4,4], k: 1, expected: [4] },
    { nums: [1,2,3,4,4,5,6,7,8,9,9,9,9], k: 2, expected: [9, 4] },
    { nums: [4,5,6,7,7,7,8,8,9,9,9,9], k: 3, expected: [9, 7, 8] }
];

testCases.forEach((test, index) => {
    console.log(`\nTest Case ${index + 1}: STARTED`);
    const result = topKFrequent(test.nums, test.k);
    console.log(`Test Case ${index + 1}: ${result.sort().toString() === test.expected.sort().toString() ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});
© d)zharii. sitemap