088 — Count Subarrays with At Most K Distinct

এতক্ষণ window-র শর্ত ছিল sum নিয়ে। এখানে শর্ত বদলায় — window-তে distinct (আলাদা) element বড়জোর K টা থাকতে পারবে। হিসাবটা আর একটা সংখ্যা নয়, একটা count map। আর প্রথমবার আমরা "কয়টা subarray" গুনব — সেই মোক্ষম নিয়ম r − l + 1। এই দুটো জিনিস — count-map invariant আর subarray গোনা — পরের কঠিন problem 089-এর ভিত। ধীরে পড়ো।

Source

• Original source: LeetCode Fruit Into Baskets (K = 2 version)-এর সাধারণীকরণ
• Platform: LeetCode — https://leetcode.com/problems/fruit-into-baskets/
• 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 গোনা)

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)।

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 পাওয়া যায়।

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-তে আসল দক্ষতা।

4. Real-life analogy

ভাবো তোমার হাতে ঠিক K রকমের রঙের ঝুড়ি (যেমন K=2 হলে দুই রকম ফল রাখার বাস্কেট — এটাই Fruit Into Baskets)। তুমি একটা সারি ধরে ফল তুলছ (ডানে এগোচ্ছ), কিন্তু বড়জোর K রকম ফলই রাখতে পারো।

K+1 তম রকম এলে — পেছন থেকে ফল ফেলতে থাকো যতক্ষণ না আবার বড়জোর K রকম হয়। প্রতিটা থামার মুহূর্তে, "এই ডান প্রান্তে শেষ হওয়া কতগুলো বৈধ টুকরো নিতে পারতাম?" — সেটাই r − l + 1।

5. Visual explanation

a = [1, 2, 1, 3], K = 2 — window distinct ≤ 2 রাখে, প্রতি r-এ r−l+1 গোনে:

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):

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-এ শেষ

6. Example input and output

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)।

7. Brute force thinking

সরল পথ — প্রতিটা subarray ধরে distinct গুনে দেখা:

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।

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 যোগ করো।

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" ধাঁচের যেকোনো গোনা হাতের মুঠোয়।

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) →	l=2	3−2+1 = 2	8

মোট 8। লক্ষ করো r=3-এ 2-এর count 0 হয়ে গেলে del করলাম — না করলে len(cnt) 3 থেকে যেত, ভুল।

12. Python solution

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

if K <= 0: return 0

distinct বড়জোর 0 মানে কোনো subarray-ই বৈধ নয় (অন্তত 1টা element থাকলে distinct ≥ 1)।

cnt = defaultdict(int) ; l = 0 ; ans = 0

cnt window-র value→count, l বাঁ প্রান্ত, ans মোট গোনা।

for r in range(len(a)):
    cnt[a[r]] += 1

a[r] window-তে ঢোকালাম; নতুন value হলে distinct বাড়ল।

    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 ঠিক করতে একাধিক বার বের করা লাগতে পারে।

    ans += r - l + 1

এখন window valid — r-এ শেষ হওয়া valid subarray-র সংখ্যা যোগ।

at_most_k_brute test যাচাইয়ের reference; random case-এ দুই পথ মিলিয়ে দেখা হয়।

14. Output walkthrough

চালালে ছাপবে:

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!।

15. Time complexity

O(n) — r মোট n বার, l-ও বড়জোর n বার; count map-এ যোগ/বিয়োগ/del গড়ে O(1)। তাই amortized O(n)।

16. Space complexity

O(min(n, K+1)) — count map-এ বড়জোর K+1 টা key থাকে (invariant ভাঙার মুহূর্তে), যা n-এর বেশি নয়। তাই O(K) ধরা যায়।

17. Common mistakes

• count 0 হওয়া key del না করা — len(cnt) distinct গোনে; 0-count key রয়ে গেলে distinct বেশি দেখায়, ভুল।
• r − l + 1 কী গুনছে গুলিয়ে ফেলা — এটা r-এ শেষ হওয়া valid subarray; প্রতি r-এ যোগ, শেষে একবার নয়।
• shrink-এ if, while না — এক ঢোকায় distinct অনেক বাড়লে কয়েকবার বের করা লাগে।
• K == 0 edge case — তখন উত্তর 0; না ধরলে while ভুল আচরণ করতে পারে।
• exactly আর at most গুলিয়ে ফেলা — এটা "বড়জোর K"; "ঠিক K" চাইলে atMost(K) − atMost(K−1) (089)।

18. Harder problems that inherit this idea

• LeetCode Fruit Into Baskets (https://leetcode.com/problems/fruit-into-baskets/) — এই idea-র K=2 রূপ (সবচেয়ে লম্বা window, দুই রকম ফল)।
• LeetCode Subarrays with K Different Integers (https://leetcode.com/problems/subarrays-with-k-different-integers/) — এই atMost-কে দুবার ব্যবহার করে exactly K (089)।
• LeetCode Longest Substring with At Most K Distinct Characters (https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/) — string-এ একই count-map window।

19. Pattern learned

Sliding window with count-map invariant + subarray counting — distinct ≤ K ধরো (count map, 0 হলে del), প্রতি r-এ ans += r − l + 1। বড় শিক্ষা: window template এক — invariant (sum/distinct) আর আউটপুট (length/count) বদলায়; "at most K" + r−l+1 = valid subarray গোনার আদর্শ জুড়ি।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "at most K distinct subarray গোনা = count-map window (0 হলে del) + প্রতি r-এ ans += r−l+1। Signal: 'at most K distinct/different, কয়টা subarray' দেখলেই এই জুড়ি মনে পড়ুক; 'exactly K' হলে দুটো atMost-এর বিয়োগ (089)।"

পরের ধাপ → 089 — Count Subarrays with Exactly K Distinct (এই atMost-কে দুবার ব্যবহার করে exactly)। ভিত্তি → 086 — Longest Subarray with Sum K।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)

Map count-invariant (distinct ≤ K), প্রতি r-এ ans += r - l + 1; 0 হলে key delete।

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, কারণ এক ঢোকায় একাধিক বার বের করা লাগতে পারে।

22. TypeScript solution (with test cases)

function atMostKDistinct(a: number[], K: number): number {
  if (K <= 0) return 0;
  const cnt = new Map<number, number>();
  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) {
      const v: number = (cnt.get(a[l]) ?? 0) - 1;
      if (v === 0) cnt.delete(a[l]);
      else cnt.set(a[l], v);
      l++;
    }
    ans += r - l + 1;
  }
  return ans;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(atMostKDistinct([1, 2, 1, 3], 2), 8, "classic");
expect(atMostKDistinct([1, 1, 1], 1), 6, "all-same");
expect(atMostKDistinct([1, 2, 3], 0), 0, "k=0");
console.log("সব TS test pass!");

TS টীকা: Map<number, number>.get দেয় number | undefined, তাই ?? 0 দিয়ে decrement নিরাপদ; cnt.size সবসময় number বলে > K তুলনা টাইপে নিশ্চিত — count-map invariant সুরক্ষিত।

23. কোথায় কাজে লাগে (real-world use)

• Diversity-constrained windows: "বড়জোর K রকম" উপাদান-সহ কতগুলো segment আছে গোনা (যেমন Fruit Into Baskets-এর K=2)।
• Cache/working-set: নির্দিষ্ট সময়ে বড়জোর K distinct key-ওয়ালা window বিশ্লেষণ।
• Network monitoring: বড়জোর K ভিন্ন protocol/host-এর টানা পর্ব গোনা।
• Inventory/menu planning: বড়জোর K রকম আইটেম রাখা যায় এমন বিন্যাস গোনা।
• Streaming analytics: at-most-K distinct গোনা থেকে exactly-K বানানো (atMost(K) − atMost(K−1))।
• Quality control: বড়জোর K ধরনের ত্রুটি-সহ টানা batch খোঁজা।

মূল pattern: window template এক — invariant (sum/distinct) আর আউটপুট (length/count) বদলায়; "at most K + কয়টা subarray" = count-map window + r − l + 1।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।