073 — Subarray Sum Equals K

এটাই এই level-এর তারকা problem — interview-তে অসম্ভব জনপ্রিয়, আর prefix sum-এর সাথে hash map-এর বিয়ে এখানেই। চাবিটা সুন্দর: subarray ধরে না খুঁজে, প্রতিটা প্রান্তে দাঁড়িয়ে জিজ্ঞেস করো "এই sum-এর জন্য দরকারি prefix কি আগে দেখেছি?" — হুবহু Two Sum-এর চাল। ধীরে পড়ো, seen[0] = 1 লাইনটা কেন লাগে সেটা বুঝে নাও — ওটাই কুখ্যাত bug।

Source

• Original source: Classic technique (prefix sum + hash map)
• Platform: LeetCode — https://leetcode.com/problems/subarray-sum-equals-k/
• 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

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), দুটো আলাদা টুকরো।

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:

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 আগে দেখেছি কি?"

3. Which basic idea does this inherit from?

মূলত 067 (Prefix Sum) থেকে — running prefix P চালিয়ে যাওয়া। কিন্তু এখানে নতুন বন্ধু হলো hash map (Python dict), যার গভীর ঘর ../../05-hashing/।

067-এ prefix বানিয়ে রাখতাম পরে query-র জন্য। এখানে prefix বানাতে বানাতেই, প্রতিটা মান কতবার এসেছে hash map-এ জমাচ্ছি, আর সাথে সাথে complement খুঁজছি। এই "prefix + complement lookup" combo টা Two Sum (hashing folder-এর প্রথম problem)-এরই বড় ভাই — সেখানে number খুঁজতাম, এখানে prefix sum খুঁজছি।

4. Real-life analogy

ভাবো তুমি একটা রাস্তায় হাঁটছ আর প্রতি ল্যাম্পপোস্টে লেখা "শুরু থেকে এখান পর্যন্ত মোট কত মিটার হাঁটলে" (এটাই prefix sum)।

তুমি জানতে চাও — কোন কোন অংশে তুমি ঠিক K মিটার হেঁটেছ। প্রতিটা ল্যাম্পপোস্টে দাঁড়িয়ে তুমি ভাবো: "এখন মোট হাঁটলাম P মিটার। তাহলে যদি আগে কোথাও ঠিক P - K মিটারে থেকে থাকি, সেখান থেকে এ পর্যন্ত অংশটা ঠিক K মিটার!"

তাই তুমি একটা নোটবুকে (hash map) লিখে রাখো প্রতিটা "মোট মিটার" মান কতবার পেরিয়েছ। প্রতি ল্যাম্পপোস্টে শুধু নোটবুক দেখো — "P - K মান কতবার লেখা আছে?" — ততগুলো বৈধ অংশ। গোটা পথ আবার মাপার দরকার নেই।

5. Visual explanation

a = [1, 2, 3], K = 3। running prefix P আর hash map seen (শুরুতে {0: 1}):

শুরু:  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] (একদম শুরু থেকে) ধরা পড়ত না।

6. Example input and output

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 এই গোনা স্বাভাবিকভাবেই সামলায়।

7. Brute force thinking

সব সম্ভাব্য (l, r) জোড়ার subarray-র sum বের করে K-এর সাথে মেলাও:

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

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

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-ও গোনা যায়। এই এক লাইন ভুললেই কিছু উত্তর হারায়।

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-এর পর থেকে) ✓।

12. Python solution

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

seen = defaultdict(int)
seen[0] = 1

hash map বানাচ্ছি (key = prefix sum মান, value = কতবার এসেছে)। seen[0] = 1 হলো base entry — "index 0-এর আগে খালি prefix একবার আছে", যাতে শুরু থেকে শুরু হওয়া subarray গোনা যায়।

P += x
count += seen[P - K]

running prefix P বাড়ালাম। তারপর জিজ্ঞেস করলাম — মান P - K আগে কতবার দেখেছি? ততগুলো নতুন valid subarray এই x-এ শেষ হচ্ছে। (defaultdict হওয়ায় না থাকলে 0 দেয়, KeyError নয়।)

seen[P] += 1

এবার নিজের prefix P map-এ জমালাম — পরের element-দের জন্য। লক্ষ করো ক্রম: আগে খোঁজো, পরে লেখো — নইলে নিজের prefix নিজেকে গুনে ভুল হতে পারে (K=0 হলে)।

বাকি assert গুলো নির্দিষ্ট উদাহরণ + random array-তে fast আর brute মিলিয়ে দেখছে (brute-force cross-check)। সব মিললে সব test pass!।

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:

2
2
সব test pass!

15. Time complexity

O(n) — array-র উপর এক pass, প্রতি element-এ একটা hash lookup আর একটা insert, দুটোই গড়ে O(1)। brute force-এর O(n²) থেকে বিশাল উন্নতি।

16. Space complexity

O(n) — খারাপ ক্ষেত্রে সব prefix sum আলাদা, তাই hash map-এ n+1 পর্যন্ত entry। input ছাড়া এটুকুই বাড়তি। (সময় বাঁচাতে জায়গা খরচ — সাধারণ trade-off।)

17. Common mistakes

1. seen[0] = 1 ভুলে যাওয়া — index 0 থেকে শুরু হওয়া subarray গোনা হয় না; এটা এই problem-এর #1 bug।
2. খোঁজা আর লেখার ক্রম উল্টানো — আগে count += seen[P-K], পরে seen[P] += 1। উল্টালে K=0-এ নিজের prefix নিজেকে গুনে বেশি আসে।
3. sliding window দিয়ে করার চেষ্টা — negative সংখ্যা থাকলে window expand/shrink-এর monotonic ধর্ম ভেঙে যায়; hash map লাগবেই।
4. শুধু একটা subarray আছে কিনা দেখা — প্রশ্ন "কতগুলো", তাই count জমাও, return-এ True/False নয়।
5. seen[P] = 1 (= বসানো, += নয়) — একই prefix sum বারবার এলে count ভুল হয়; সবসময় += 1 দিয়ে frequency জমাও।

18. Harder problems that inherit this idea

• LeetCode — Subarray Sum Equals K (https://leetcode.com/problems/subarray-sum-equals-k/) — ঠিক এই problem।
• LeetCode — Continuous Subarray Sum (https://leetcode.com/problems/continuous-subarray-sum/) — prefix + hash map, কিন্তু mod-এর key দিয়ে (074-এর দিকে সেতু)।
• 074 (Count Subarrays Divisible by K) — এই repo-তে পরের ধাপ: একই hash চাল, P-K-র জায়গায় P % K।
• গভীর hashing → ../../05-hashing/problems/013-subarray-sum-equals-k.md (একই problem hashing-এর চোখে)।

19. Pattern learned

Prefix sum + hash map (complement lookup) — sum = K কে P[l-1] = P[r] - K বানিয়ে hash map-এ frequency খোঁজা; seen[0] = 1 দিয়ে শুরু। বড় শিক্ষা: subarray ঘুরে না খুঁজে প্রান্তে দাঁড়িয়ে "দরকারি prefix আগে দেখেছি?" জিজ্ঞেস করো — এটা Two Sum-এর complement চালের subarray রূপ।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "sum = K গোনা = prefix + hash map; প্রতি step count += seen[P-K]; seen[P] += 1, শুরুতে seen[0] = 1। negative থাকলে sliding window নয়, hash map। আগে খোঁজো, পরে লেখো।"

পরের ধাপ → 074 — Count Subarrays Divisible by K (একই চাল, P-K-র জায়গায় P % K)।

ফিরে দেখা: শিকড় → 067 — Prefix Sum · গভীর hashing → ../../05-hashing/ · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)

JS-এ frequency রাখতে Map ব্যবহার করি, আর সেই কুখ্যাত seen[0] = 1 হয় seen.set(0, 1)।

// 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 নিজেকে গুনবে।

22. TypeScript solution (with test cases)

function subarraySumK(a: number[], K: number): number {
  const seen = new Map<number, number>();
  seen.set(0, 1);
  let P = 0, count = 0;
  for (const x of a) {
    P += x;
    count += seen.get(P - K) ?? 0;
    seen.set(P, (seen.get(P) ?? 0) + 1);
  }
  return count;
}

function expect(actual: number, expected: number, msg = ""): void {
  if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}

const cases: ReadonlyArray<readonly [number[], number, number]> = [
  [[1, 2, 3], 3, 2], [[1, 1, 1], 2, 2], [[-1, -1, 1], 0, 1],
  [[1], 0, 0], [[0, 0, 0], 0, 6],
];
for (const [arr, K, want] of cases) expect(subarraySumK(arr, K), want, `[${arr}],K=${K}`);
console.log("সব TS test pass!");

TS টীকা: Map<number, number> লিখলে key/value দুটোই number-এ বাঁধা — ভুলে string key বসানো compile-time-এ ধরা পড়ে; এটাই plain-object string-key bug-টা ভাষাগতভাবে আটকায়। ?? 0 (nullish) দিয়ে missing key নিরাপদে 0।

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

• Range/target detection in streams: কোনো metric-এর running sum ঠিক target ছুঁলো কিনা — billing window, quota, anomaly detection।
• Balanced/zero-sum segment: net change 0 এমন অংশ খোঁজা (লাভ-ক্ষতি সমান, charge সমান) — K = 0 কেস।
• Continuous subarray with property (mod K): একই hash চাল P % K দিয়ে — divisibility, hashing-এ।
• Two Sum-গোত্রের complement খোঁজা: "দরকারি জিনিস আগে দেখেছি?" — caching/dedup/lookup-এর সাধারণ চাল। মূল pattern — "subarray ঘুরো না; prefix + hash map-এ 'দরকারি prefix আগে দেখেছি?' (O(n²) → O(n))" — complement lookup, sliding-window-বিকল্প জুড়ে বড় ছবিতে ফেরে।

---

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