Problem link ও উৎস
- **Original source:** LeetCode Fruit Into Baskets (K = 2 version)-এর সাধারণীকরণ
- **Platform:** LeetCode —
- **Topic:** Sliding window → count map invariant + subarray counting
- **Difficulty:** Medium
- **Pattern:** window + count map (distinct ≤ K invariant; ans += r−l+1)
- **Basic idea inherited from:** 086 — Longest Subarray with Sum K (একই grow/shrink, তবে invariant এখন distinct গোনা)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `a` আর একটা সংখ্যা `K` দেওয়া। গুনতে হবে কতগুলো পরপর subarray আছে যাদের ভেতরে **আলাদা মানের সংখ্যা বড়জোর K টা** (অর্থাৎ distinct count ≤ K)।
খেয়াল করো — "ঠিক K" নয়, "বড়জোর K"। তাই 1, 2, ..., K — সব distinct count-এর subarray গোনা হয়। এই "at most" রূপটাই পরে "exactly K" বানানোর হাতিয়ার (089)।
### Input ও output {#6-example-input-and-output}
```text
a K -> count
-----------------------------
[1, 2, 1, 3] 2 -> 8
[1, 2, 1, 2, 3] 2 -> 12
[1, 2, 3] 1 -> 3 (শুধু একক element subarray)
[1, 1, 1] 1 -> 6 (সব subarray-ই distinct 1)
[1, 2, 3] 3 -> 6 (সব 6টা subarray valid)
[] 2 -> 0
```
Edge case: `K == 0` হলে কোনো valid subarray নেই (0); খালি array → 0; `K >= distinct মোট` হলে সব subarray valid (n·(n+1)/2)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার হাতে ঠিক `K` রকমের রঙের ঝুড়ি (যেমন K=2 হলে দুই রকম ফল রাখার বাস্কেট — এটাই Fruit Into Baskets)। তুমি একটা সারি ধরে ফল তুলছ (ডানে এগোচ্ছ), কিন্তু বড়জোর K রকম ফলই রাখতে পারো।
K+1 তম রকম এলে — পেছন থেকে ফল ফেলতে থাকো যতক্ষণ না আবার বড়জোর K রকম হয়। প্রতিটা থামার মুহূর্তে, "এই ডান প্রান্তে শেষ হওয়া কতগুলো বৈধ টুকরো নিতে পারতাম?" — সেটাই `r − l + 1`।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
**086 — Longest Subarray with Sum K**-এর grow/shrink কাঠামো হুবহু এক। শুধু দুটো বদল:
- **invariant** — 086-এ ছিল "sum"; এখানে "distinct count ≤ K", হিসাবটা একটা count map
- **আউটপুট** — 086-এ দৈর্ঘ্য; এখানে **গোনা** (`ans += r − l + 1`)
মানে template একই থাকে — `for r: ঢোকাও; while শর্ত-ভাঙা: l থেকে বের করো` — শুধু "s" এর জায়গায় "cnt" আর শর্তটা ভিন্ন। এই "template এক, invariant বদলায়" উপলব্ধিটাই sliding window-তে আসল দক্ষতা।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
দুটো idea একসাথে:
1. **Count-map invariant** — window-র distinct সংখ্যা ধরে রাখতে একটা `value → কতবার` map; distinct মানে map-এ ক'টা key (`len(cnt)`)। শর্ত: `len(cnt) <= K`।
2. **Subarray গোনার নিয়ম** — window `[l..r]` যদি সবচেয়ে বড় valid window হয় (r ঠিক রেখে), তাহলে **r-এ শেষ হওয়া** valid subarray-র সংখ্যা = `r − l + 1` (শুরু l থেকে r পর্যন্ত যেকোনো জায়গা)।
প্রতিটা r-এ এই সংখ্যাটা যোগ করলে মোট valid subarray পাওয়া যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরল পথ — প্রতিটা subarray ধরে distinct গুনে দেখা:
```python
def at_most_k_brute(a, K):
n = len(a)
total = 0
for i in range(n):
seen = set()
for j in range(i, n):
seen.add(a[j])
if len(seen) <= K:
total += 1
else:
break # আর বাড়ালে distinct শুধু বাড়বে
return total
```
ঠিক উত্তর দেয় — প্রতিটা শুরু থেকে distinct বাড়তে বাড়তে K ছাড়ালে থামে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো nested loop — প্রায় n²/2 subarray। n = 100000 হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।
```text
n = 100000 হলে:
brute force : ~5,000,000,000 subarray (O(n²))
sliding window: বড়জোর ~200000 move (O(n))
```
মূল অপচয়: window distinct-ও monotonic-ঘেঁষা (ডানে বাড়ে, বাঁ থেকে কমে) — একটা চলন্ত window-ই যথেষ্ট, তবু brute প্রতিটা শুরু থেকে নতুন set বানাচ্ছে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **একটা window রাখো distinct ≤ K invariant ধরে; প্রতি r-এ r−l+1 যোগ করো।**
```text
cnt = {}, l = 0, ans = 0
for r in range(n):
cnt[a[r]] += 1 # ঢোকাও
while len(cnt) > K: # distinct বেশি → বাঁ বের
cnt[a[l]] -= 1
if cnt[a[l]] == 0: del cnt[a[l]]
l += 1
ans += r - l + 1 # r-এ শেষ হওয়া সব valid subarray
return ans
```
`del` করা আবশ্যক — value 0 হওয়া key রয়ে গেলে `len(cnt)` ভুল হবে।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
দুটো "আহা!" একসাথে:
1. **invariant বদলেছে, template না** — sum-এর জায়গায় count map, "s > k" এর জায়গায় "len(cnt) > K"; বাকি grow/shrink হুবহু 086।
2. **গোনার নিয়ম r − l + 1** — প্রতিটা r-এ valid window `[l..r]`-এর ভেতর যত শুরু, তত subarray r-এ শেষ হয়; ছোট window আরো নিরাপদ বলে সবগুলো valid।
এই দুটো জিনিস হাতে এলে "at most K" ধাঁচের যেকোনো গোনা হাতের মুঠোয়।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [1, 2, 1, 3]`, `K = 2` — window distinct ≤ 2 রাখে, প্রতি r-এ `r−l+1` গোনে:
```text
a = [ 1 , 2 , 1 , 3 ]
r=0: [1] cnt={1:1} distinct 1 ≤2 ✓ → ans += (0-0+1)=1 মোট 1
r=1: [1 2] cnt={1:1,2:1} distinct 2 ≤2 ✓ → ans += (1-0+1)=2 মোট 3
r=2: [1 2 1] cnt={1:2,2:1} distinct 2 ≤2 ✓ → ans += (2-0+1)=3 মোট 6
r=3: [1 2 1 3] distinct 3 >2 ✗ → বাঁ বের: l=0(1→1), l=1(2→0,del) → [1 3] distinct 2 ✓
→ ans += (3-2+1)=2 মোট 8
উত্তর = 8
```
`r − l + 1` কী গুনছে (r=2, l=0):
```text
r-এ শেষ হওয়া valid subarray: [1..2]=[1,2,1] , [2..2]=[2,1] , [2..2 শুরু l+1..]=[1]
দৈর্ঘ্য 3 = (2 − 0 + 1) → তিনটে: শুরু index 0, 1, 2 — সব r=2-এ শেষ
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [1, 2, 1, 3]`, `K = 2`। `cnt={}, l=0, ans=0`:
| r | a[r] | cnt (ঢোকার পর) | len>2? while বের | cnt, l পরে | ans += r−l+1 | ans |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 1 | {1:1} | না | l=0 | 0−0+1 = 1 | 1 |
| 1 | 2 | {1:1,2:1} | না | l=0 | 1−0+1 = 2 | 3 |
| 2 | 1 | {1:2,2:1} | না | l=0 | 2−0+1 = 3 | 6 |
| 3 | 3 | {1:2,2:1,3:1} | হ্যাঁ: l=0(1→1), l=1(2→0 del) → {1:1,3:1} | l=2 | 3−2+1 = 2 | 8 |
মোট **8**। লক্ষ করো r=3-এ 2-এর count 0 হয়ে গেলে `del` করলাম — না করলে `len(cnt)` 3 থেকে যেত, ভুল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from collections import defaultdict
def at_most_k_distinct(a, K):
"""distinct ≤ K এমন subarray-র সংখ্যা ফেরত দেয়।"""
if K <= 0:
return 0
cnt = defaultdict(int)
l = 0
ans = 0
for r in range(len(a)):
cnt[a[r]] += 1 # ঢোকাও
while len(cnt) > K: # distinct বেশি → বাঁ বের
cnt[a[l]] -= 1
if cnt[a[l]] == 0:
del cnt[a[l]] # 0 হলে মুছতেই হবে, নইলে len ভুল
l += 1
ans += r - l + 1 # r-এ শেষ হওয়া সব valid subarray
return ans
def at_most_k_brute(a, K):
"""ধীর reference — প্রতিটা subarray-র distinct গুনে যাচাই।"""
n = len(a)
total = 0
for i in range(n):
seen = set()
for j in range(i, n):
seen.add(a[j])
if len(seen) <= K:
total += 1
else:
break
return total
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert at_most_k_distinct([1, 2, 1, 3], 2) == 8
assert at_most_k_distinct([1, 2, 1, 2, 3], 2) == 12
assert at_most_k_distinct([1, 2, 3], 1) == 3
assert at_most_k_distinct([1, 1, 1], 1) == 6
assert at_most_k_distinct([1, 2, 3], 3) == 6
assert at_most_k_distinct([], 2) == 0
assert at_most_k_distinct([1, 2, 3], 0) == 0
# brute force-এর সাথে মিলিয়ে দেখা (নানা random case)
import random
random.seed(29)
for _ in range(500):
n = random.randint(0, 12)
arr = [random.randint(1, 4) for _ in range(n)]
K = random.randint(0, 5)
assert at_most_k_distinct(arr, K) == at_most_k_brute(arr, K), (arr, K)
print(at_most_k_distinct([1, 2, 1, 3], 2)) # 8
print(at_most_k_distinct([1, 2, 1, 2, 3], 2)) # 12
print(at_most_k_distinct([1, 1, 1], 1)) # 6
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
if K <= 0: return 0
```
distinct বড়জোর 0 মানে কোনো subarray-ই বৈধ নয় (অন্তত 1টা element থাকলে distinct ≥ 1)।
```text
cnt = defaultdict(int) ; l = 0 ; ans = 0
```
`cnt` window-র value→count, `l` বাঁ প্রান্ত, `ans` মোট গোনা।
```text
for r in range(len(a)):
cnt[a[r]] += 1
```
`a[r]` window-তে ঢোকালাম; নতুন value হলে distinct বাড়ল।
```text
while len(cnt) > K:
cnt[a[l]] -= 1
if cnt[a[l]] == 0: del cnt[a[l]]
l += 1
```
distinct K ছাড়ালে বাঁ থেকে বের করি; count 0 হলে key মুছি (নইলে `len` ভুল)। `while` কারণ এক ঢোকায় invariant ঠিক করতে একাধিক বার বের করা লাগতে পারে।
```text
ans += r - l + 1
```
এখন window valid — r-এ শেষ হওয়া valid subarray-র সংখ্যা যোগ।
`at_most_k_brute` test যাচাইয়ের reference; random case-এ দুই পথ মিলিয়ে দেখা হয়।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
8
12
6
সব test pass!
```
প্রথম লাইন `[1,2,1,3]` K=2 → 8; দ্বিতীয় লাইন `[1,2,1,2,3]` K=2 → 12; তৃতীয় লাইন `[1,1,1]` K=1 → 6 (সব 6টা subarray)। তার আগে 500 random case brute-force-এর সাথে মিলেছে, তাই `সব test pass!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
`Map` count-invariant (distinct ≤ K), প্রতি r-এ `ans += r - l + 1`; 0 হলে key delete।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// number of subarrays with at most K distinct values
function atMostKDistinct(a, K) {
if (K <= 0) return 0;
const cnt = new Map();
let l = 0, ans = 0;
for (let r = 0; r < a.length; r++) {
cnt.set(a[r], (cnt.get(a[r]) || 0) + 1); // ঢোকাও
while (cnt.size > K) { // distinct বেশি -> বাঁ বের
const v = cnt.get(a[l]) - 1;
if (v === 0) cnt.delete(a[l]); // 0 হলে মুছতেই হবে, নইলে size ভুল
else cnt.set(a[l], v);
l++;
}
ans += r - l + 1; // r-এ শেষ হওয়া সব valid subarray
}
return ans;
}
// ---- test cases (example + edge) ----
assert(atMostKDistinct([1, 2, 1, 3], 2) === 8, "classic");
assert(atMostKDistinct([1, 2, 1, 2, 3], 2) === 12, "longer");
assert(atMostKDistinct([1, 2, 3], 1) === 3, "k=1");
assert(atMostKDistinct([1, 1, 1], 1) === 6, "all-same");
assert(atMostKDistinct([1, 2, 3], 3) === 6, "k=all");
assert(atMostKDistinct([], 2) === 0, "empty"); // edge
assert(atMostKDistinct([1, 2, 3], 0) === 0, "k=0"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** distinct count = `cnt.size` (Map-এর key সংখ্যা)। count 0 হলে অবশ্যই `cnt.delete(...)` — না করলে 0-value key রয়ে গিয়ে `size` ভুল distinct দেখাবে। shrink-এ `if` নয় `while`, কারণ এক ঢোকায় একাধিক বার বের করা লাগতে পারে।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
function atMostKDistinct(a: number[], K: number): number {
if (K <= 0) return 0;
const cnt = new Map