347. Top K Frequent Elements

function topKFrequent(nums: number[], k: number): number[] {
    let hash = new Map<number, number>()
    let freqArray = []

    // Iterating over the nums length to calculate the frequency of elements
    for (let i = 0; i < nums.length; i++) {
        if (hash.has(nums[i])) {
            hash.set(nums[i], hash.get(nums[i]) + 1)
        } else {
            hash.set(nums[i], 1)
        }
    }

    //A new array freqArray is constructed where the index represents frequency,
    // each entry at index i is an array of numbers that appear i times in nums
    for (let [key, val] of hash) {
        if (!freqArray[val]) freqArray[val] = []
        freqArray[val].push(key)
    }

    // The freqArray is iterated in reverse to ensure that the most frequent elements are considered first.
    // This loop runs at most n times (once for each unique frequency).
    // The inner loop runs at most k times because it stops once the result array res has k elements. 
    // However, since the inner loop will only execute fully for one frequency count (because it breaks once res has k elements).
    let res = []
    for (let x = freqArray.length - 1; x >= 0; x--) {
        if (!freqArray[x]) continue;

        for (let num of freqArray[x]) {
            if (res.length === k) break
            res.push(num)
        }
    }

    return res
};        

Total Time Complexity: The total time complexity is the sum of these parts, which is O(n) for the hash map creation, O(n) for the frequency array construction, and O(n) for the result construction, resulting in O(n) + O(n) + O(n), which simplifies to O(n), where n is the number of elements in nums.

Space Complexity: The space complexity is O(n) for the hash map, O(n) for the frequency array (in the worst case where all elements are unique and appear only once), and O(k) for the result array. Since k is at most n, this results in O(n) space complexity.