Problem link ও উৎস
- **Original source:** Classic technique (prefix sum + hash map)
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
- **Difficulty:** Medium
- **Pattern:** prefix sum + hash map (complement lookup)
- **Basic idea inherited from:** 067 — Prefix Sum
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার array `a` (negative-ও থাকতে পারে) আর একটা সংখ্যা `K` দেওয়া। তোমাকে বলতে হবে — কতগুলো **contiguous subarray** (পরপর element-এর টুকরো) আছে যাদের sum ঠিক `K`?
মানে শুধু একটা খুঁজে পেলে হবে না, **মোট কতগুলো** আছে গুনতে হবে। যেমন `a = [1, 1, 1], K = 2` হলে উত্তর 2 — `[1,1]` (index 0-1) আর `[1,1]` (index 1-2), দুটো আলাদা টুকরো।
### Input ও output {#6-example-input-and-output}
```text
a K -> count কোন subarray গুলো
-------------------------------------------------------------------
[1, 2, 3] 3 -> 2 [1,2], [3]
[1, 1, 1] 2 -> 2 [1,1] (0-1), [1,1] (1-2)
[3, 4, 7, 2, -3, 1, 4, 2] 7 -> 4 (overlap সহ একাধিক)
[-1, -1, 1] 0 -> 1 [-1,1] (1-2)
[1] 0 -> 0 কোনোটাই নয়
[0, 0, 0] 0 -> 6 সব টুকরো (0 দিয়ে বহু combination)
```
Edge case খেয়াল করো: **negative সংখ্যা** থাকতে পারে (`[-1,-1,1]`) — তাই sliding window চলবে না, hash map লাগবেই। আর `[0,0,0], K=0` → 6, কারণ 0 অনেকভাবে জোড়া বাঁধে: hash map এই গোনা স্বাভাবিকভাবেই সামলায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি একটা রাস্তায় হাঁটছ আর প্রতি ল্যাম্পপোস্টে লেখা **"শুরু থেকে এখান পর্যন্ত মোট কত মিটার হাঁটলে"** (এটাই prefix sum)।
তুমি জানতে চাও — কোন কোন অংশে তুমি ঠিক `K` মিটার হেঁটেছ। প্রতিটা ল্যাম্পপোস্টে দাঁড়িয়ে তুমি ভাবো: "এখন মোট হাঁটলাম `P` মিটার। তাহলে যদি আগে কোথাও ঠিক `P - K` মিটারে থেকে থাকি, সেখান থেকে এ পর্যন্ত অংশটা ঠিক `K` মিটার!"
তাই তুমি একটা নোটবুকে (hash map) লিখে রাখো প্রতিটা "মোট মিটার" মান কতবার পেরিয়েছ। প্রতি ল্যাম্পপোস্টে শুধু নোটবুক দেখো — "`P - K` মান কতবার লেখা আছে?" — ততগুলো বৈধ অংশ। গোটা পথ আবার মাপার দরকার নেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
মূলত **067 (Prefix Sum)** থেকে — running prefix `P` চালিয়ে যাওয়া। কিন্তু এখানে নতুন বন্ধু হলো **hash map** (Python `dict`), যার গভীর ঘর [../../05-hashing/](../../../05-hashing/README.md)।
067-এ prefix বানিয়ে রাখতাম পরে query-র জন্য। এখানে prefix বানাতে বানাতেই, প্রতিটা মান কতবার এসেছে hash map-এ জমাচ্ছি, আর সাথে সাথে complement খুঁজছি। এই "prefix + complement lookup" combo টা Two Sum (hashing folder-এর প্রথম problem)-এরই বড় ভাই — সেখানে number খুঁজতাম, এখানে prefix sum খুঁজছি।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **prefix sum + complement খোঁজা hash map দিয়ে**।
`P[r]` = প্রথম r+1 টা element-এর মোট ধরো। তাহলে subarray `(l..r)`-এর sum = `P[r] - P[l-1]`। আমরা চাই এটা `K`:
```text
P[r] - P[l-1] = K ⟺ P[l-1] = P[r] - K
```
মানে r-এ দাঁড়িয়ে প্রশ্ন: "`P[r] - K` মানের prefix আগে কতবার এসেছে?" যতবার এসেছে, ততগুলো নতুন valid subarray। আগের সব prefix কতবার করে এসেছে সেটা একটা hash map-এ রাখলেই এক pass-এ গোনা যায়। এটা Two Sum-এর হুবহু চাল — "complement আগে দেখেছি কি?"
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সব সম্ভাব্য `(l, r)` জোড়ার subarray-র sum বের করে K-এর সাথে মেলাও:
```python
def subarray_sum_k_brute(a, K):
n = len(a)
count = 0
for l in range(n):
s = 0
for r in range(l, n): # l থেকে শুরু করে r বাড়াই
s += a[r] # running sum (প্রতিবার গোড়া থেকে না)
if s == K:
count += 1
return count
```
সরল, ঠিক উত্তর দেয় — প্রতিটা শুরু `l`-এর জন্য `r` বাড়িয়ে sum জমায়, K মিললে count বাড়ায়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো nested loop — প্রতিটা শুরু `l`-এর জন্য সব শেষ `r`। মোট subarray সংখ্যা প্রায় `n²/2`, তাই **O(n²)**।
```text
n = 20000 হলে:
brute force: ~2 × 10^8 operation (O(n²)) — বড় input-এ TLE
hash way : ~20000 operation (এক pass, O(n))
```
অপচয়টা কোথায়? প্রতিটা `l`-এর জন্য আবার ডান দিকে হাঁটছি — অথচ prefix sum দিয়ে "কতবার আগে দরকারি মান এসেছে" সরাসরি জানা যায়, পুরো বাঁ দিক আবার না ঘুরে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: subarray `(l..r)`-এর sum = `P[r] - P[l-1]`, তাই sum = K মানে `P[l-1] = P[r] - K`। প্রতিটা r-এ শুধু জানতে হবে মান `P[r] - K` আগে কতবার এসেছে — সেটা hash map থেকে O(1):
```python
def subarray_sum_k(a, K):
from collections import defaultdict
seen = defaultdict(int)
seen[0] = 1 # খালি prefix — index 0 থেকে শুরু subarray-র জন্য
P = 0
count = 0
for x in a:
P += x
count += seen[P - K] # আগে কতবার P-K দেখেছি = তত নতুন subarray
seen[P] += 1 # নিজের prefix এখন জমা
return count
```
এক pass, প্রতি step O(1) — মোট **O(n)**। O(n²) থেকে নেমে এল।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **subarray গুনতে subarray ঘুরো না — প্রান্তে দাঁড়িয়ে জিজ্ঞেস করো "দরকারি prefix কি আগে দেখেছি?"** `sum = P[r] - P[l-1] = K` কে উল্টে `P[l-1] = P[r] - K` লেখাটাই পুরো চাল — এটা Two Sum-এর "complement খোঁজা"-রই রূপ।
দ্বিতীয়, কম-আলোচিত কিন্তু সমান গুরুত্বপূর্ণ tweak: **`seen[0] = 1` দিয়ে শুরু করো।** এটা বলে "index 0-এর আগে একটা খালি prefix (মান 0) আছে" — যাতে একদম শুরু থেকে শুরু হওয়া subarray-ও গোনা যায়। এই এক লাইন ভুললেই কিছু উত্তর হারায়।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [1, 2, 3], K = 3`। running prefix `P` আর hash map `seen` (শুরুতে `{0: 1}`):
```text
শুরু: seen = {0: 1}, P = 0, count = 0
(seen[0] = 1 মানে: "খালি prefix একবার দেখেছি" — index 0 থেকে শুরু subarray-র জন্য)
x = 1: P = 0 + 1 = 1
খুঁজি P - K = 1 - 3 = -2 → seen-এ নেই (0 বার)
seen[1] += 1 → seen = {0:1, 1:1}
x = 2: P = 1 + 2 = 3
খুঁজি P - K = 3 - 3 = 0 → seen-এ আছে 1 বার! count = 1 ([1,2])
seen[3] += 1 → seen = {0:1, 1:1, 3:1}
x = 3: P = 3 + 3 = 6
খুঁজি P - K = 6 - 3 = 3 → seen-এ আছে 1 বার! count = 2 ([3])
seen[6] += 1 → seen = {0:1, 1:1, 3:1, 6:1}
উত্তর: count = 2 → [1,2] আর [3]
```
মূল কথা: প্রতি step-এ আগে **খোঁজো** (complement `P-K` কতবার), তারপর **নিজেরটা লেখো**। ক্রমটা উল্টালে নিজের prefix নিজেকে গোনার ভুল হতে পারে। আর `seen[0] = 1` ছাড়া `[1,2]` (একদম শুরু থেকে) ধরা পড়ত না।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [1, 1, 1], K = 2`। শুরুতে `seen = {0: 1}`, `P = 0`, `count = 0`:
| x | P += x | খুঁজি P - K | seen-এ কতবার | count | seen আপডেট |
| --- | --- | --- | --- | --- | --- |
| 1 | 1 | 1 - 2 = -1 | 0 | 0 | {0:1, 1:1} |
| 1 | 2 | 2 - 2 = 0 | 1 | 1 | {0:1, 1:1, 2:1} |
| 1 | 3 | 3 - 2 = 1 | 1 | 2 | {0:1, 1:1, 2:1, 3:1} |
শেষ অবস্থা: `count = 2`। দুটো subarray: প্রথম দুই 1 (P=2-এ P-K=0 পেলাম, খালি prefix থেকে) আর শেষ দুই 1 (P=3-এ P-K=1 পেলাম, প্রথম 1-এর পর থেকে) ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from collections import defaultdict
def subarray_sum_k(a, K):
"""sum ঠিক K এমন contiguous subarray-র সংখ্যা; prefix + hash map, O(n)।"""
seen = defaultdict(int)
seen[0] = 1 # খালি prefix (index 0 থেকে শুরুর জন্য) — কুখ্যাত bug-এর রক্ষাকবচ
P = 0
count = 0
for x in a:
P += x
count += seen[P - K] # আগে P-K কতবার = তত নতুন subarray
seen[P] += 1
return count
def subarray_sum_k_brute(a, K):
"""ধীর O(n^2) version — মিলিয়ে দেখার জন্য।"""
n = len(a)
count = 0
for l in range(n):
s = 0
for r in range(l, n):
s += a[r]
if s == K:
count += 1
return count
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert subarray_sum_k([1, 2, 3], 3) == 2
assert subarray_sum_k([1, 1, 1], 2) == 2
assert subarray_sum_k([3, 4, 7, 2, -3, 1, 4, 2], 7) == 4 # overlap সহ
assert subarray_sum_k([-1, -1, 1], 0) == 1 # negative
assert subarray_sum_k([1], 0) == 0
assert subarray_sum_k([0, 0, 0], 0) == 6 # 0-এর বহু জোড়া
# fast আর brute একই উত্তর কিনা (random brute-force cross-check):
import random
random.seed(17)
for _ in range(500):
arr = [random.randint(-3, 3) for _ in range(random.randint(0, 10))]
K = random.randint(-5, 5)
assert subarray_sum_k(arr, K) == subarray_sum_k_brute(arr, K)
print(subarray_sum_k([1, 2, 3], 3)) # 2
print(subarray_sum_k([1, 1, 1], 2)) # 2
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
seen = defaultdict(int)
seen[0] = 1
```
hash map বানাচ্ছি (key = prefix sum মান, value = কতবার এসেছে)। `seen[0] = 1` হলো base entry — "index 0-এর আগে খালি prefix একবার আছে", যাতে শুরু থেকে শুরু হওয়া subarray গোনা যায়।
```text
P += x
count += seen[P - K]
```
running prefix `P` বাড়ালাম। তারপর জিজ্ঞেস করলাম — মান `P - K` আগে কতবার দেখেছি? ততগুলো নতুন valid subarray এই `x`-এ শেষ হচ্ছে। (`defaultdict` হওয়ায় না থাকলে 0 দেয়, KeyError নয়।)
```text
seen[P] += 1
```
এবার নিজের prefix `P` map-এ জমালাম — পরের element-দের জন্য। লক্ষ করো ক্রম: **আগে খোঁজো, পরে লেখো** — নইলে নিজের prefix নিজেকে গুনে ভুল হতে পারে (K=0 হলে)।
বাকি `assert` গুলো নির্দিষ্ট উদাহরণ + random array-তে fast আর brute মিলিয়ে দেখছে (brute-force cross-check)। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
`a = [1, 2, 3], K = 3`:
- x=1: P=1, খুঁজি -2 (নেই), count=0, seen={0:1,1:1}
- x=2: P=3, খুঁজি 0 (আছে 1), count=1, seen={0:1,1:1,3:1}
- x=3: P=6, খুঁজি 3 (আছে 1), count=2, seen={...,6:1}
- return 2 → প্রথম `print` ছাপে `2`
- `subarray_sum_k([1,1,1], 2)` → 2 → দ্বিতীয় `print` ছাপে `2`
- সব `assert` pass → `সব test pass!`
ছাপা output:
```text
2
2
সব test pass!
```
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
JS-এ frequency রাখতে `Map` ব্যবহার করি, আর সেই কুখ্যাত `seen[0] = 1` হয় `seen.set(0, 1)`।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function subarraySumK(a, K) {
const seen = new Map();
seen.set(0, 1); // খালি prefix — index 0 থেকে শুরুর জন্য (রক্ষাকবচ)
let P = 0, count = 0;
for (const x of a) {
P += x;
count += seen.get(P - K) || 0; // আগে P-K কতবার = তত নতুন subarray
seen.set(P, (seen.get(P) || 0) + 1); // নিজের prefix জমা
}
return count;
}
// brute O(n^2) — cross-check
function subarraySumKBrute(a, K) {
let count = 0;
for (let l = 0; l < a.length; l++) {
let s = 0;
for (let r = l; r < a.length; r++) { s += a[r]; if (s === K) count++; }
}
return count;
}
// ---- test cases (file-এর example + edge case) ----
assert(subarraySumK([1, 2, 3], 3) === 2, "[1,2],[3]");
assert(subarraySumK([1, 1, 1], 2) === 2, "two windows");
assert(subarraySumK([3, 4, 7, 2, -3, 1, 4, 2], 7) === 4, "overlap");
assert(subarraySumK([-1, -1, 1], 0) === 1, "negative");
assert(subarraySumK([1], 0) === 0, "none");
assert(subarraySumK([0, 0, 0], 0) === 6, "0-এর বহু জোড়া");
// fast == brute, random ছোট array জুড়ে
for (let t = 0; t < 500; t++) {
const n = Math.floor(Math.random() * 9);
const arr = [];
for (let i = 0; i < n; i++) arr.push(Math.floor(Math.random() * 7) - 3); // -3..3
const K = Math.floor(Math.random() * 11) - 5; // -5..5
assert(subarraySumK(arr, K) === subarraySumKBrute(arr, K), "cross-check");
}
console.log("সব JS test pass!");
```
> **JS টীকা:** plain object `{}`-এর key string হয়ে যায় (negative/large prefix-এ ভুল), তাই numeric key রাখতে `Map` ব্যবহার করো। `seen.get(k)` না থাকলে `undefined` দেয় — `|| 0` দিয়ে সামলাও (Python `defaultdict(int)`-এর বদলি)। আর ক্রম: আগে `get(P-K)`, পরে `set(P)` — উল্টালে K=0-এ নিজের prefix নিজেকে গুনবে।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
function subarraySumK(a: number[], K: number): number {
const seen = new Map