21) Top K Frequent Elements

Sorta floundered about and got here:

function topKFrequent(nums: number[], k: number): number[] {
    // so I'm thinking a map
    // where Map<the Number, incrementing count of those elements>
    // the trickier part is the sorting I think, at the end. where I take a map
    // wait what? How many numbers am I supposed to return?
 
    const kMap: Map<number, number> = new Map()
 
    for (let num of nums){
        if (!kMap.has(num)){
            kMap.set(num, 1)
        } else {
            kMap.set(num, Kmap.get(num)+1)
        }
    }
 
    const nar = Array.from(kMap)
    console.log(nar)
};

But what I was missing was an idea for how to sort the map, and really everything on this last crazy line in this example I found:

function topKFrequent(nums: number[], k: number): number[] {
    // so I'm thinking a map
    // where Map<the Number, incrementing count of those elements>
    // the trickier part is the sorting I think, at the end. where I take a map
    // wait what? How many numbers am I supposed to return?
 
    const kMap: Map<number, number> = new Map()
 
    for (let num of nums){
        if (!kMap.has(num)){
            kMap.set(num, 1)
        } else {
            kMap.set(num, kMap.get(num)+1)
        }
    }
 
    return [...kMap.entries()].sort((a,b)=>b[1]-a[1]).map(num=>num[0]).slice(0,k)
}

So sick! The sorting function, map to return first element, and slice I probably would have gotten to eventually, but they were sort of overwhelming me.

In the context of interviewing, it definitely would be a good idea to just break them down into multiple lines, verbosely if necessary, any way I knew how.

But it is also nice to see this succinct way of doing things.

Sweet, reproduced it:

function topKFrequent(nums: number[], k: number): number[] {
    const numMap = new Map()
 
    for (const num of nums){
        if (numMap.has(num)){
            const current = numMap.get(num)
            numMap.set(num, current+1)
        } else {
            numMap.set(num, 1)
        }
    }
 
    return [...numMap.entries()].sort((a, b)=>b[1]-a[1]).map(n=>n[0]).slice(0, k)
};

I think the thing I grok the least here is the sort function to be honest. How does b-a evaluate in a useful way? It’s clearly an iteration over the map of some kind, that evaluates relationships.

Okay so looking here, and there is an optional compare function that can be passed in, which defines how custom sorting happens.

The compare function has the following form:

function compareFn(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  } else if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

Okay…that makes sense, but doesn’t really apply to b[1]-a[1] as far as I can tell, because this statement could return all sorts of integers, positive or negative, besides 1 and -1.

Ah okay, here’s the real definition:

compareFn(a, b) return value	sort order
> 0	sort a after b, e.g. [b, a]
< 0	sort a before b, e.g. [a, b]
=== 0	keep original order of a and b
Okay let me just grok this in human language.

If we run our compare function with arguments (a,b), if return value is more than 0, sort a after b. So positive leads to b,a, ordering. If a is 10, and be is 5, then a-b would result in a positive, and this to b,a sorting order.

Return 1

Time to completion: 3:47

function topKFrequent(nums: number[], k: number): number[] {
    const numMap: Map<number, number> = new Map()
    for (let num of nums){
        if (numMap.has(num)){
            let current = numMap.get(num)
            numMap.set(num, current+1)
        } else {
            numMap.set(num, 1)
        }
    }
 
    return [...numMap.entries()].sort((a, b)=>b[1]-a[1]).map(n=>n[0]).slice(0,k)
};

Tried using const numMap: Map<number, number[]> which is I supposed an approach that could work, but is probably an unnecessary expensive space complexity.

I did find myself wondering if there was a more efficient way to do the type of map manipulation I am doing, where I check if a map has an entry and then immediately change that entry, otherwise setting it to a default value.

First off, I have to ask the question, why use .has instead of just .get on maps?

It turns out that one reason is that if the key to get is falsy, this can kind of mess things up. Not really an issue here though.

Claude says we can get ride of a TON of lines:

function topKFrequent(nums: number[], k: number): number[] {
    const numMap = new Map<number, number>();
    nums.forEach(num => numMap.set(num, (numMap.get(num) || 0) + 1));
    
    return [...numMap.entries()]
        .sort((a, b) => b[1] - a[1])
        .slice(0, k)
        .map(([num]) => num);
}

Wow. Okay so we have this forEach…then for each, we TRY to get a value, and if it’s undefined, we default it to 0, and we add 1 regardless. Beautiful! This is so cool. Let me try to implement this from memory.

function topKFrequent(nums: number[], k: number): number[] {
    const numMap: Map<number, number> = new Map()
    nums.forEach(num => numMap.set(num, (numMap.get(num) || 0) + 1))
    return [...numMap.entries()].sort((a, b)=>b[1]-a[1]).map(n=>n[0]).slice(0,k)
};

Wow, got it!

Time to completion: 3:16

Technically a three liner. I like how claude split up the dots. Also, the 3rd line is definitely not readable, but it is cool that it CAN be one line.