Oreo's Top K Treats (Bucket Sort)

My name is Oreo, and I'm a data-driven persian with a serious treat addiction. My human keeps giving me different snacks throughout the day, but I got curious - which treats am I getting the most? Time to put my programming paws to work!

The Great Treat Mystery 🤔

So there I was, lying in my favorite sunny spot, when I started wondering: "What are my TOP treats?" I mean, I get shrimp 🍤, chicken 🍗, cookies 🍪, and fish 🐟 regularly, but which ones appear most frequently in my daily feast?

Being the sophisticated feline I am, I decided to solve this programmatically. This is a classic "Top K Frequent Elements" problem, and I'm going to solve it in O(treats) time and O(treats) space using bucket sort. Purr-fect!

My Treat Data 📊

Here's what my human gave me recently:

const treats = ["🍤", "🍗", "🍪", "🐟", "🍤", "🍪", "🍗", "🐟", "🍪", "🍤"]
const k = 2  // I want my top 2 treats

Hmm, looks like cookies and shrimp are showing up a lot... but let me verify this scientifically!

Step 1: Counting My Treats 🧮

First, I need to count how many times each treat appears. I'll use a Map for this:

const map = new Map()

for (const treat of treats) {
    map.set(treat, (map.get(treat) || 0) + 1)
}

This is like keeping a mental tally every time my human gives me a treat. "Oh, another shrimp! That's number 3..." you know how it goes.

After this loop, my map looks like:

• 🍤 (shrimp): 3 times
• 🍗 (chicken): 2 times
• 🍪 (cookies): 3 times
• 🐟 (fish): 2 times

Step 2: The Bucket Sort Magic ✨

Here's where it gets interesting! Instead of sorting (which would be O(n log n)), I'm using bucket sort. I create buckets where the index represents the frequency:

const buckets = Array(treats.length + 1).fill(null).map(() => [])

for (const [treat, freq] of map) {
    buckets[freq].push(treat)
}

Think of this as organizing my treats into frequency boxes. Box 1 has treats that appeared once, box 2 has treats that appeared twice, etc.

My buckets now look like:

• buckets[0]: [] (empty - no treats appeared 0 times)
• buckets[1]: [] (empty - all treats appeared more than once)
• buckets[2]: [🍗, 🐟] (chicken and fish appeared 2 times each)
• buckets[3]: [🍤, 🍪] (shrimp and cookies appeared 3 times each)
• buckets[4] through buckets[10]: [] (empty)

Step 3: Finding My Top K Treats 🏆

Now I traverse the buckets from highest frequency to lowest, collecting treats until I have my top K:

const result = []

outer: for (let i = buckets.length - 1; i > 0; i--) {
    const currentBucket = buckets[i];
    if (currentBucket.length === 0) continue;

    for (const item of currentBucket) {
        result.push(item);
        if (result.length === k) break outer;
    }
}

I start from the highest frequency bucket and work my way down.

The Moment of Truth! 🎉

console.log(topKFrequent(treats, k))
// Output: ["🍤", "🍪"]

Aha! My top 2 treats are shrimp 🍤 and cookies 🍪, each appearing 3 times. My sophisticated palate was right all along!

Why This Approach is Purr-fect 🐾

Time Complexity: O(n) - I go through my treats once to count, once to put in buckets, and once to collect results. Linear time, just like how I eat treats in a straight line!

Space Complexity: O(n) - I use a map to store treat counts and buckets to organize by frequency. The space grows linearly with the number of treats.

This bucket sort approach is much more efficient than traditional sorting methods for this specific problem.

The Complete Solution 💻

var topKFrequent = function (treats, k) {
    const map = new Map()
    const buckets = Array(treats.length + 1).fill(null).map(() => [])
    const result = []

    // Count treat frequencies
    for (const treat of treats) {
        map.set(treat, (map.get(treat) || 0) + 1)
    }

    // Place treats in frequency buckets
    for (const [treat, freq] of map) {
        buckets[freq].push(treat)
    }

    // Collect top K treats from highest frequency buckets
    outer: for (let i = buckets.length - 1; i > 0; i--) {
        const currentBucket = buckets[i];
        if (currentBucket.length === 0) continue;

        for (const item of currentBucket) {
            result.push(item);
            if (result.length === k) break outer;
        }
    }

    return result
};

Final Thoughts 💭

Well, now I know scientifically that shrimp and cookies are my favorites! Time to demand more of these from my human. This bucket sort approach is elegant because it leverages the constraint that frequencies can't exceed the array length, making it perfect for this type of problem.

Now if you'll excuse me, I have some high-frequency treats to go demand... 🍤🍪