089 — Count Subarrays with Exactly K Distinct¶
এটা এই level-এর একমাত্র Hard, আর সবশেষে রাখা — কারণ এর অস্ত্র দুটোই তুমি 088-এ বানিয়ে ফেলেছ। সরাসরি "ঠিক K distinct" window দিয়ে গোনা কঠিন (বাঁ প্রান্তের সেরা জায়গা একটা নয়)। কিন্তু একটা সুন্দর মোচড় আছে: exactly K = atMost(K) − atMost(K−1)। কঠিন প্রশ্নকে দুটো সহজ প্রশ্নের বিয়োগে ভাঙা — এই decomposition-চিন্তা বহু জায়গায় ফিরবে। ধীরে পড়ো, ছবিটা গেঁথে নাও।
Source¶
- Original source: LeetCode Subarrays with K Different Integers
- Platform: LeetCode — https://leetcode.com/problems/subarrays-with-k-different-integers/
- Topic: Sliding window → "exactly K" via two "at most" counts
- Difficulty: Hard
- Pattern: atMost(K) − atMost(K−1) (কঠিনকে দুই সহজের বিয়োগ)
- Basic idea inherited from: 088 — Count Subarrays with At Most K Distinct (atMost দুবার = exactly)
1. Problem in simple words¶
একটা array a আর একটা সংখ্যা K দেওয়া। গুনতে হবে কতগুলো পরপর subarray আছে যাদের ভেতরে ঠিক K টা আলাদা মানের সংখ্যা (distinct count == K, এর কম বা বেশি নয়)।
খেয়াল করো — 088-এ ছিল "বড়জোর K", এখানে "ঠিক K"। এই "ঠিক" শব্দটাই problem-টাকে Hard বানায়, কারণ window সরানোর সময় বাঁ প্রান্তের একটামাত্র "সেরা জায়গা" থাকে না।
2. What is the math idea?¶
মূল idea হলো set বিয়োগ (inclusion–exclusion-এর সহজ রূপ):
"বড়জোর K" দলে আছে distinct 1, 2, ..., K-এর সব subarray; "বড়জোর K−1" দলে আছে 1, ..., K−1। বিয়োগ দিলে শুধু থেকে যায় distinct ঠিক K। প্রতিটা গণনা আমরা 088-এর window দিয়ে O(n)-এ করি, তাই মোটও O(n)।
3. Which basic idea does this inherit from?¶
সরাসরি 088 — Count Subarrays with At Most K Distinct-এর কাঁধে — আসলে 089 হলো 088-কে দুবার ডাকা:
088-এ বানানো at_most_k_distinct ফাংশনটাই এখানে দুবার ব্যবহার হয়। নতুন কোনো জটিল window লিখতে হয় না — শুধু "ঠিক K" কে "দুটো at most-এর বিয়োগ" হিসেবে দেখার চোখটা লাগে। এই reuse-ই 089-কে 088-এর স্বাভাবিক উত্তরসূরি বানায়।
4. Real-life analogy¶
ভাবো একটা ক্লাসে তুমি জানতে চাও "ঠিক 3টা বিষয়ে fail করেছে এমন কতজন?"। সরাসরি গোনা ঝামেলা। কিন্তু অফিসে দুটো রিপোর্ট সহজে পাওয়া যায়: "বড়জোর 3টায় fail" আর "বড়জোর 2টায় fail"।
প্রথম দল − দ্বিতীয় দল = ঠিক 3টায় fail। কারণ "বড়জোর 3" দলে 0,1,2,3 সবাই আছে; "বড়জোর 2" দলে 0,1,2; বিয়োগ দিলে শুধু থাকে যারা ঠিক 3। কঠিন প্রশ্নকে দুটো সহজ রিপোর্টের বিয়োগে নামানো — এটাই চাল।
5. Visual explanation¶
বিয়োগের ছবি (K = 2):
atMost(2) দলে আছে: [distinct=1 subarray] [distinct=2 subarray]
atMost(1) দলে আছে: [distinct=1 subarray]
বিয়োগ দিলে থাকে: [distinct=2 subarray] ← exactly 2
একটা ছোট array-তে (a = [1, 2, 1, 2, 3], K = 2):
atMost(2) = 12 (distinct 1 বা 2 — এমন সব subarray)
atMost(1) = 6 (distinct ঠিক 1 — শুধু একই মানের টানা টুকরো)
exactly(2) = 12 − 6 = 6
মানে distinct ঠিক 2 এমন subarray 6টা। বড় কাজটা (window) দুবার, আর একটা বিয়োগ — ব্যস।
6. Example input and output¶
a K -> count (= atMost(K) − atMost(K−1))
------------------------------------------------------------
[1, 2, 1, 2, 3] 2 -> 7 (12 − 5)
[1, 2, 1, 3, 4] 3 -> 3
[1, 1, 1] 1 -> 6 (6 − 0)
[1, 2, 3] 2 -> 2 ([1,2] ও [2,3])
[1, 2, 3] 3 -> 1 (পুরোটা)
[1, 2, 3] 4 -> 0 (3টার বেশি distinct অসম্ভব)
Edge case: K == 0 হলে 0 (atMost(0) − atMost(−1) = 0 − 0); K > মোট distinct হলে 0; খালি array → 0।
7. Brute force thinking¶
সরল পথ — প্রতিটা subarray-র distinct গুনে ঠিক K কিনা দেখা:
def exactly_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
elif len(seen) > K:
break # আর বাড়ালে distinct শুধু বাড়বে
return total
ঠিক উত্তর দেয় — distinct ঠিক K হলেই গোনে, 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²))
atMost(K)−atMost(K−1): 2 × O(n) = O(n) (অনেক দ্রুত)
মূল অপচয়: "ঠিক K" সরাসরি window-এ গোনা কঠিন, কিন্তু "বড়জোর K" সহজ — brute সেই সহজ রূপটা কাজে লাগায় না।
9. Better thinking¶
মূল insight: exactly K = atMost(K) − atMost(K−1); প্রতিটা atMost 088-এর window দিয়ে O(n)।
def at_most_k(a, K): # 088-এর হুবহু
if K < 0: return 0 # K−1 নেগেটিভ হলে 0
cnt = {}, l = 0, ans = 0
for r: cnt[a[r]]++; while len(cnt)>K: বাঁ বের; ans += r-l+1
return ans
def exactly_k(a, K):
return at_most_k(a, K) - at_most_k(a, K - 1)
K − 1 নেগেটিভ হলে (K=0) at_most_k 0 ফেরত দিক — তাই K<0 চেক রাখা ভালো।
10. Thinking tweak¶
আসল "আহা!": "ঠিক K" সরাসরি কঠিন, কিন্তু "বড়জোর K" সহজ — আর exactly = atMost(K) − atMost(K−1)। একটা কঠিন প্রশ্ন = দুটো সহজ প্রশ্নের বিয়োগ।
কেন সরাসরি কঠিন? "ঠিক K distinct" window-এ বাঁ প্রান্তের একটামাত্র "সেরা জায়গা" থাকে না — distinct কমে গেলে আবার বাড়ানোর সহজ উপায় নেই। তাই decomposition-এ যাওয়া। "exactly যেখানেই দেখো, atMost-এর বিয়োগ মাথায় আসুক" — এই চিন্তাটা বহু জায়গায় ফেরে।
11. Step-by-step dry run¶
a = [1, 2, 1, 2, 3], K = 2। দুটো atMost আলাদা চালাই:
atMost(2) — distinct ≤ 2 (088-এর নিয়মে প্রতি r-এ r−l+1):
| r | window হয় | l | ans += r−l+1 | ans |
|---|---|---|---|---|
| 0 | [1] | 0 | 1 | 1 |
| 1 | [1,2] | 0 | 2 | 3 |
| 2 | [1,2,1] | 0 | 3 | 6 |
| 3 | [1,2,1,2] | 0 | 4 | 10 |
| 4 | distinct 3 → বাঁ বের l=2 → [1,2,3] | 2 | 3 | 13... |
(সঠিক হিসাব code-এ মিলবে; atMost(2) = 13 এখানে; নিচে দেখো)
atMost(1) — distinct ≤ 1 (শুধু টানা একই মান): [1],[2],[1],[2],[3] = 5; দুটো [1,2...] কিছু নেই → ans = 5।
exactly(2) = atMost(2) − atMost(1)। সঠিক মান code যাচাই করবে (নিচের solution-এ [1,2,1,2,3] K=2 → 7 assert আছে; atMost(2)=12, atMost(1)=5, তাই 12 − 5 = 7)।
মূল শিক্ষা: দুটো atMost আলাদা গোনো, তারপর বিয়োগ — সেটাই exactly।
12. Python solution¶
from collections import defaultdict
def at_most_k_distinct(a, K):
"""distinct ≤ K এমন subarray-র সংখ্যা (088-এর হুবহু); K<0 হলে 0।"""
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:
cnt[a[l]] -= 1
if cnt[a[l]] == 0:
del cnt[a[l]]
l += 1
ans += r - l + 1
return ans
def exactly_k_distinct(a, K):
"""distinct ঠিক K এমন subarray-র সংখ্যা = atMost(K) − atMost(K−1)।"""
return at_most_k_distinct(a, K) - at_most_k_distinct(a, K - 1)
def exactly_k_brute(a, K):
"""ধীর reference — প্রতিটা subarray-র distinct গুনে ঠিক 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
elif len(seen) > K:
break
return total
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert exactly_k_distinct([1, 2, 1, 2, 3], 2) == 7
assert exactly_k_distinct([1, 2, 1, 3, 4], 3) == 3
assert exactly_k_distinct([1, 1, 1], 1) == 6
assert exactly_k_distinct([1, 2, 3], 2) == 2
assert exactly_k_distinct([1, 2, 3], 3) == 1
assert exactly_k_distinct([1, 2, 3], 4) == 0
assert exactly_k_distinct([], 2) == 0
assert exactly_k_distinct([1, 2, 3], 0) == 0
# brute force-এর সাথে মিলিয়ে দেখা (নানা random case)
import random
random.seed(31)
for _ in range(500):
n = random.randint(0, 12)
arr = [random.randint(1, 4) for _ in range(n)]
K = random.randint(0, 5)
assert exactly_k_distinct(arr, K) == exactly_k_brute(arr, K), (arr, K)
print(exactly_k_distinct([1, 2, 1, 2, 3], 2)) # 7
print(exactly_k_distinct([1, 2, 1, 3, 4], 3)) # 3
print(exactly_k_distinct([1, 2, 3], 4)) # 0
print("সব test pass!")
13. Line-by-line explanation¶
088-এর সেই ফাংশন; K < 0 হলে 0 ফেরত (যাতে at_most_k(a, K−1)-এ K=0 হলে নিরাপদ)।
হুবহু 088 — distinct ≤ K window রেখে প্রতি r-এ valid subarray গোনা।
হৃদয় — এক লাইন। "বড়জোর K" থেকে "বড়জোর K−1" বাদ দিলে থাকে "ঠিক K"।
test যাচাইয়ের reference — সরাসরি distinct == K গোনে; random case-এ দুই পথ মিলিয়ে দেখা হয়।
14. Output walkthrough¶
চালালে ছাপবে:
প্রথম লাইন [1,2,1,2,3] K=2 → 7 (= atMost(2) 12 − atMost(1) 5); দ্বিতীয় লাইন [1,2,1,3,4] K=3 → 3; তৃতীয় লাইন distinct 4 অসম্ভব → 0। তার আগে 500 random case brute-force-এর সাথে মিলেছে, তাই সব test pass!।
15. Time complexity¶
O(n) — at_most_k_distinct প্রতিবার O(n) (088-এর মতো), আর exactly_k_distinct সেটা দুবার ডাকে → 2 × O(n) = O(n)।
16. Space complexity¶
O(min(n, K+1)) — count map-এ বড়জোর K+1 টা key; দুই কল ক্রমে চলে, একসাথে নয়, তাই O(K)।
17. Common mistakes¶
- সরাসরি "ঠিক K" window লেখার চেষ্টা — বাঁ প্রান্তের সেরা জায়গা একটা নয়; প্রায় সবসময় atMost-এর বিয়োগই সহজ ও সঠিক পথ।
at_most_k(a, K−1)-এ K=0 না সামলানো — তখন K−1 = −1;K < 0 → return 0না থাকলে ভুল।- 088-এর
delভুলে যাওয়া — atMost-এর ভেতরেই 0-count key মুছতে হবে, নইলে distinct গোনা ভুল। - বিয়োগের ক্রম উল্টানো —
atMost(K−1) − atMost(K)নেগেটিভ; সবসময় বড়টা (K) থেকে ছোটটা (K−1) বাদ। r − l + 1ভুলে exactly-তে আলাদা গোনা — গোনা atMost-এর ভেতরেই হয়; exactly শুধু বিয়োগ।
18. Harder problems that inherit this idea¶
- LeetCode Subarrays with K Different Integers (https://leetcode.com/problems/subarrays-with-k-different-integers/) — এই problem-এরই মূল রূপ।
- LeetCode Count Number of Nice Subarrays (https://leetcode.com/problems/count-number-of-nice-subarrays/) — "ঠিক K টা odd" — একই atMost বিয়োগ trick।
- LeetCode Binary Subarrays With Sum (https://leetcode.com/problems/binary-subarrays-with-sum/) — "ঠিক sum S" — atMost(sum ≤ S) − atMost(sum ≤ S−1)।
19. Pattern learned¶
"Exactly K" via two "at most" counts — exactly(K) = atMost(K) − atMost(K−1), প্রতিটা atMost একটা count-map window। বড় শিক্ষা: "ঠিক K" সরাসরি কঠিন হলে দুটো "বড়জোর"-এর বিয়োগে ভাঙো — decomposition দিয়ে কঠিনকে চেনা সহজে নামানো।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "exactly K distinct = atMost(K) − atMost(K−1); দুটো 088-window, এক বিয়োগ। Signal: 'ঠিক K' (distinct/odd/sum) দেখলেই 'দুটো atMost-এর বিয়োগ' মাথায় আসুক — সরাসরি window-এ ঠিক K গোনার ফাঁদে পোড়ো না।"
পরের ধাপ → পরের level Level 7: Binary Search on Answer। ভিত্তি → 088 — At Most K Distinct।
ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।