Problem link ও উৎস
- **Original source:** Classic frequency + bucket-sort exercise
- **Platform:** LeetCode —
- **Topic:** hash map (Counter) + bucket sort
- **Difficulty:** Medium
- **Pattern:** frequency counting
- **Basic idea inherited from:** Counter + bucket idea — গুনে ফেলো, তারপর frequency নিয়ে ভাবো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার array `nums` আর একটা সংখ্যা `k` দেওয়া আছে। যে `k`টা element সবচেয়ে **বেশিবার** এসেছে, সেগুলো ফেরত দিতে হবে। উত্তরের ক্রম যেকোনো হতে পারে।
```text
nums = [1, 1, 1, 2, 2, 3], k = 2
1 এসেছে 3 বার, 2 এসেছে 2 বার, 3 এসেছে 1 বার
→ সবচেয়ে frequent 2টা: [1, 2]
```
### Input ও output {#8-example-input-and-output}
```text
Input : nums = [1,1,1,2,2,3], k = 2 Output: [1, 2] (ক্রম যেকোনো)
Input : nums = [1], k = 1 Output: [1]
Input : nums = [4,4,4,5,5,6], k = 2 Output: [4, 5]
Input : nums = [1,2,3,4], k = 4 Output: [1,2,3,4]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা ভোটগণনা: প্রথমে প্রতিটা প্রার্থীর ভোট গুনে ফেললে (Counter)। এবার পুরস্কার দিতে তুমি প্রার্থীদের নাম sort করো না — বরং "যার 100 ভোট সে এই তাকে, যার 99 ওই তাকে" করে ভোটসংখ্যা ধরে তাক সাজাও (bucket)। সবচেয়ে উঁচু তাক থেকে নিচে নামতে নামতে প্রথম k জন বিজয়ী তুলে নাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **frequency counting** (Pattern 1)-এর সরাসরি সন্তান। আগে শিখেছ এক pass-এ `value → count` বানাতে। এখানে সেই count বানানোর পর আরেক ধাপ: count অনুযায়ী top-k বের করা। নতুন কৌশল হলো **bucket idea** — count-কেই index বানিয়ে sort এড়ানো।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
দুই স্তরের logic। প্রথমত, কোনো element কতবার এসেছে সেটা একটা hash map-এ গুনে রাখা যায়। দ্বিতীয়ত — একটা সূক্ষ্ম পর্যবেক্ষণ — n দৈর্ঘ্যের array-তে কোনো frequency কখনো **n-এর বেশি হতে পারে না**। তাই frequency-গুলো `0..n` সীমার মধ্যে; এই সীমিত range-কে কাজে লাগিয়ে comparison-sort (O(n log n)) এড়িয়ে bucket দিয়ে O(n)-এ top-k তোলা যায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো জিনিস:
- একটা **Counter** (`collections.Counter`), অর্থাৎ `value → frequency` hash map।
- একটা **bucket array**, যেখানে `buckets[f]` ধরে রাখে যেসব value-র frequency ঠিক `f`। index নিজেই frequency বলে দেয়, তাই আলাদা sort লাগে না।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Counter এক pass-এ O(n)-এ গোনা শেষ করে। আর frequency যেহেতু `0..n`-এ আবদ্ধ, একটা `(n+1)`-দৈর্ঘ্যের bucket array-তে value-দের frequency ধরে বসিয়ে দিলে বড় frequency থেকে নিচে নামতে নামতে প্রথম `k`টা তুলে নেওয়া যায় — পুরোটাই O(n)। Heap দিয়েও হয় (O(n log k)), কিন্তু bucket এখানে আরও পরিষ্কার ও দ্রুত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা distinct value-র frequency গোনো, তারপর সব (value, frequency) জোড়াকে frequency অনুযায়ী **descending sort** করে প্রথম k-টা নাও।
```text
count = প্রতিটা value-র frequency
pairs = count.items() কে frequency অনুযায়ী বড় থেকে ছোট sort
return প্রথম k-টা value
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
Sort করা মানে **O(n log n)** (distinct value সংখ্যার উপর)। অথচ আমাদের পুরো ক্রম দরকার নেই — শুধু উপরের k-টা চাই। আর frequency-গুলো `0..n`-এ সীমাবদ্ধ থাকায় comparison-sort পুরোটাই অপ্রয়োজনীয়; সীমিত range মানেই counting/bucket দিয়ে O(n)-এ সারা যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **frequency নিজেই একটা ছোট, সীমিত সংখ্যা (0 থেকে n)।** তাই frequency-কে array-র index বানিয়ে value-দের সেখানে ফেলে দেওয়া যায়; উঁচু index থেকে নিচে নামলেই descending ক্রম বিনামূল্যে পাওয়া যায় — কোনো comparison sort ছাড়াই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রথমে `Counter(nums)`। তারপর `(n+1)`-দৈর্ঘ্যের `buckets` বানাও; প্রতিটা `(value, freq)`-কে `buckets[freq]`-এ রাখো। এবার `freq = n` থেকে `1` পর্যন্ত নিচে নামো, প্রতিটা bucket-এর value-গুলো নিতে থাকো, ঠিক `k`টা হলে থামো। পুরোটা **O(n)** time।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** *raw item নিয়ে ভেবো না — count নিয়ে ভাবো, আর count যদি সীমিত range-এ থাকে তবে sort না করে index বানাও।* এই দ্বিতীয় অংশটাই Pattern 1-কে এক ধাপ এগিয়ে নেয়: counting + bucket = O(n) selection।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1,1,1,2,2,3]`, `k = 2`। প্রথমে Counter, তারপর frequency-কে index ধরে bucket:
```text
Counter: {1: 3, 2: 2, 3: 1}
bucket index (frequency): 0 1 2 3
[ ] [3] [2] [1]
উঁচু থেকে নিচে: freq=3 → 1 নাও (result=[1])
freq=2 → 2 নাও (result=[1,2]) → len == k, থামো
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums = [1,1,1,2,2,3]`, `k = 2`:
1. `count = {1: 3, 2: 2, 3: 1}`।
2. `buckets`: index 3 → `[1]`, index 2 → `[2]`, index 1 → `[3]`, বাকি খালি।
3. `freq = 6..4`: সব খালি, কিছু নেওয়া হলো না।
4. `freq = 3`: `1` নাও → `result = [1]`।
5. `freq = 2`: `2` নাও → `result = [1, 2]` → `len == k`, return `[1, 2]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums) # value -> frequency
buckets = [[] for _ in range(len(nums) + 1)] # index = frequency
for num, freq in count.items():
buckets[freq].append(num)
result = []
for freq in range(len(buckets) - 1, 0, -1): # বেশি frequency আগে
for num in buckets[freq]:
result.append(num)
if len(result) == k:
return result
return result
# ---- tests ----
assert set(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == {1, 2}
assert top_k_frequent([1], 1) == [1]
assert set(top_k_frequent([4, 4, 4, 5, 5, 6], 2)) == {4, 5}
assert set(top_k_frequent([1, 2, 3, 4], 4)) == {1, 2, 3, 4}
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `count = Counter(nums)` — এক pass-এ প্রতিটা value-র frequency।
- `buckets = [[] for _ in range(len(nums) + 1)]` — index 0..n; index মানেই frequency।
- `for num, freq in count.items(): buckets[freq].append(num)` — প্রতিটা value তার frequency-bucket-এ।
- `for freq in range(len(buckets) - 1, 0, -1)` — সবচেয়ে বড় frequency থেকে নিচে নামি।
- `result.append(num)` ও `if len(result) == k: return result` — k-টা হয়ে গেলেই থামি।
- test-এ `set(...)` দিয়ে মেলাই, কারণ সমান-frequency element-দের ক্রম যেকোনো হতে পারে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,1,1,2,2,3]`-এ Counter `{1:3, 2:2, 3:1}`; bucket[3]=[1], bucket[2]=[2], bucket[1]=[3]। উঁচু থেকে নিচে নেমে `1` তারপর `2` নিয়ে k=2 পূর্ণ → `{1,2}`। `[1,2,3,4]` k=4-এ সবার frequency 1, bucket[1]=[1,2,3,4]; সব নিয়ে `{1,2,3,4}`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
`Map`-এ count, তারপর frequency-কে index ধরে bucket — sort এড়িয়ে O(n)।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
const sameSet = (a, b) =>
JSON.stringify([...a].sort((x, y) => x - y)) === JSON.stringify([...b].sort((x, y) => x - y));
// k most frequent elements (count + bucket sort)
function topKFrequent(nums, k) {
const count = new Map(); // value -> frequency
for (const x of nums) count.set(x, (count.get(x) || 0) + 1);
const buckets = Array.from({ length: nums.length + 1 }, () => []); // index = frequency
for (const [num, freq] of count) buckets[freq].push(num);
const result = [];
for (let freq = buckets.length - 1; freq > 0; freq--) { // বেশি frequency আগে
for (const num of buckets[freq]) {
result.push(num);
if (result.length === k) return result;
}
}
return result;
}
// ---- test cases (example + edge); সমান-frequency-তে ক্রম যেকোনো, তাই set-compare ----
assert(sameSet(topKFrequent([1, 1, 1, 2, 2, 3], 2), [1, 2]), "classic");
assert(sameSet(topKFrequent([1], 1), [1]), "single");
assert(sameSet(topKFrequent([4, 4, 4, 5, 5, 6], 2), [4, 5]), "two");
assert(sameSet(topKFrequent([1, 2, 3, 4], 4), [1, 2, 3, 4]), "all-tie"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** bucket array `Array.from({length: n+1}, () => [])` দিয়ে বানাও — `new Array(n).fill([])` দিলে সব একই array reference share করত (bug)। সমান-frequency element-দের ক্রম arbitrary, তাই assert-এ set-compare।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function topKFrequent(nums: number[], k: number): number[] {
const count = new Map