কনটেন্টে যান

073 — Subarray Sum Equals K

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

Problem link ও উৎস

  • 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা সংখ্যার 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

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

চেনা উদাহরণে বোঝা

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

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

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

মূলত 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 খুঁজছি।

ভেতরের অঙ্ক

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সব সম্ভাব্য (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 বাড়ায়।

কোথায় বেশি কাজ হতে পারে

দুটো 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 দিয়ে "কতবার আগে দরকারি মান এসেছে" সরাসরি জানা যায়, পুরো বাঁ দিক আবার না ঘুরে।

আরও ভালোভাবে ভাবা

মূল 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²) থেকে নেমে এল।

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

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

ছোট input-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

উদাহরণ
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!।

Output মিলিয়ে দেখা

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!

JavaScript ও 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

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

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

  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 জমাও।

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

কৌশলটি মনে রাখুন

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 রূপ।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "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।

কোথায় কাজে লাগে

  • 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" লেখো।