কনটেন্টে যান

013 — Subarray Sum Equals K

Problem link ও উৎস

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

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

একটা সংখ্যার array nums (ঋণাত্মকও থাকতে পারে) আর একটা সংখ্যা k দেওয়া আছে। গুনতে হবে কতগুলো contiguous subarray (পরপর element-এর টুকরো) আছে যাদের যোগফল ঠিক k।

উদাহরণ
nums = [1, 1, 1], k = 2
subarray যাদের যোগ 2: [1,1] (index 0–1) আর [1,1] (index 1–2)
উত্তর: 2

Input ও output

উদাহরণ
Input : nums = [1,1,1], k = 2            Output: 2
Input : nums = [1,2,3], k = 3            Output: 2   ([1,2] আর [3])
Input : nums = [1],     k = 0            Output: 0
Input : nums = [-1,-1,1], k = 0          Output: 1   ([-1,1])
Input : nums = [3,4,7,2,-3,1,4,2], k=7   Output: 4

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

ভাবো তুমি প্রতিদিনের শেষে ব্যাংকের মোট জমা (running total) একটা খাতায় টুকে রাখছ। কেউ জিজ্ঞেস করল "কোন কোন সময়ের ব্যবধানে ঠিক k টাকা ঢুকেছে?" তুমি প্রতিটা দিনের জোড়া মেলাও না — আজকের মোট থেকে k বাদ দিয়ে দেখো "এই মোটটা আগে কতদিন ছিল?" তোমার খাতার সেই গণনা-নোটই hash map; প্রতিটা পুরোনো ম্যাচ একটা বৈধ ব্যবধান।

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

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

এটা দুটো ভিত্তির সংকর। প্রথমটা prefix sum — math fundamentals-এর ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/-এ শেখা: যেকোনো range-এর যোগ দুটো prefix-এর বিয়োগফল। দ্বিতীয়টা Two Sum-এর complement lookup (#1)। দুটো মিলিয়ে এই problem আক্ষরিক অর্থে "prefix value-র উপর করা Two Sum"। ../patterns.md-তে এটা Pattern 5।

ভেতরের যুক্তি

ধরো prefix[i] মানে শুরু থেকে index i পর্যন্ত যোগফল। তাহলে (i, j] range-এর যোগ = prefix[j] - prefix[i]। আমরা চাই এই বিয়োগফল = k, অর্থাৎ prefix[i] = prefix[j] - k। তাই প্রতিটা j-তে প্রশ্নটা দাঁড়ায়: এ পর্যন্ত কতগুলো prefix-এর মান ছিল ঠিক prefix[j] - k? — হুবহু Two Sum-এর complement প্রশ্ন, শুধু value-র জায়গায় running prefix।

কী দিয়ে তথ্য রাখব

একটা hash map (prefix value → কতবার এসেছে)। শুধু "complement prefix আছে কি?" জানলে হবে না — কতবার এসেছে সেটাও দরকার, কারণ আমরা subarray গুনছি, প্রথমটা খুঁজছি না। তাই value হিসেবে count রাখি (defaultdict(int) সুবিধাজনক)।

এটি কেন উপযুক্ত

প্রতিটা j-তে আমরা জিজ্ঞেস করি "অতীতে prefix - k কতবার দেখেছি?" — hash map এটা গড়ে O(1)-এ দেয়, আর এক pass-এ count জমিয়ে রাখে। ফলে পুরো গোনা O(n)। সব জোড়া (i, j) ধরে যোগফল মেলালে O(n^2) লাগত; hash map সেই অতীত-খোঁজাকে instant করে।

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

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

প্রথম সরল চিন্তা: প্রতিটা শুরু i থেকে প্রতিটা শেষ j পর্যন্ত যোগফল হিসেব করে দেখো k কি না।

উদাহরণ
count = 0
প্রতিটা শুরু i-র জন্য:
    running = 0
    প্রতিটা j >= i-র জন্য:
        running += nums[j]
        running == k হলে count += 1
return count

কোথায় বেশি কাজ হচ্ছে

দুটো nested loop মানে O(n^2)। অপচয়টা Two Sum-এর মতোই: প্রতিটা শুরু-বিন্দুর জন্য আমরা বারবার একই অঞ্চলের যোগফল নতুন করে বের করছি, যদিও running total একবার রাখলেই যেকোনো range-এর যোগ বিয়োগফলে পাওয়া যায়। জানা জিনিস (complement prefix) খুঁজতে scan লাগে না।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: range-এর প্রশ্নকে দুটো prefix-এর প্রশ্নে বদলে ফেলা যায়। subarray sum = k মানে prefix[j] - prefix[i] = k, অর্থাৎ আমরা এমন আগের prefix খুঁজছি যার মান prefix[j] - k। ব্যস — এটা এখন Two Sum, শুধু সংখ্যা নয়, running prefix-এর উপর।

আরও কম কাজে সমাধান

এক pass-এ running prefix রাখো। শুরুতে seen = {0: 1} (খালি prefix একবার ঘটে)। প্রতিটা element-এ: prefix update করো, তারপর count += seen[prefix - k] (এই complement prefix অতীতে যতবার ছিল, ততগুলো নতুন subarray শেষ হলো এখানে), তারপর seen[prefix] += 1। মোট O(n)।

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

মোচড়: range যোগফলের প্রশ্নকে "pair-of-prefixes" প্রশ্নে অনুবাদ করো, তারপর search না করে remember করো। এটা Two Sum-এর tweak-এর সরাসরি প্রয়োগ — শুধু "value" এখন "এ পর্যন্ত যোগফল"। এই অনুবাদটাই পুরো prefix-sum + hash map pattern-এর প্রাণ।

ছবিতে বোঝা

nums = [1,1,1], k = 2। prefix চলে, seen (prefix → count) ভরে; prefix - k কতবার দেখা = নতুন subarray:

উদাহরণ
শুরু: prefix=0, seen={0:1}, count=0
x=1: prefix=1, need 1-2=-1 → seen[-1]=0; count=0; seen={0:1, 1:1}
x=1: prefix=2, need 2-2=0  → seen[0]=1; count=1; seen={0:1, 1:1, 2:1}
x=1: prefix=3, need 3-2=1  → seen[1]=1; count=2; seen={0:1, 1:1, 2:1, 3:1}
উত্তর: 2

seen={0:1} দিয়ে শুরু — যাতে একদম শুরু থেকে যোগ হওয়া subarray-ও গোনা যায়।

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

Input nums = [1, 2, 3], k = 3:

  1. শুরু: prefix = 0, seen = {0: 1}, count = 0।
  2. x = 1: prefix = 1; need 1-3 = -2; seen[-2] = 0 → count 0; seen = {0:1, 1:1}।
  3. x = 2: prefix = 3; need 3-3 = 0; seen[0] = 1 → count 1; seen = {0:1, 1:1, 3:1}।
  4. x = 3: prefix = 6; need 6-3 = 3; seen[3] = 1 → count 2; seen = {0:1,1:1,3:1,6:1}।
  5. উত্তর: 2 — subarray [1,2] ও [3]।

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

Python

Python
from collections import defaultdict

def subarray_sum(nums, k):
    count = 0
    prefix = 0
    seen = defaultdict(int)
    seen[0] = 1                        # খালি prefix একবার ধরা
    for x in nums:
        prefix += x
        count += seen[prefix - k]      # complement prefix কতবার দেখেছি
        seen[prefix] += 1
    return count

# ---- tests ----
assert subarray_sum([1, 1, 1], 2) == 2
assert subarray_sum([1, 2, 3], 3) == 2
assert subarray_sum([1], 0) == 0
assert subarray_sum([-1, -1, 1], 0) == 1
assert subarray_sum([3, 4, 7, 2, -3, 1, 4, 2], 7) == 4
print("সব test pass!")

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

  • count = 0, prefix = 0 — মোট উত্তর আর running যোগফল।
  • seen = defaultdict(int); seen[0] = 1 — খালি prefix একবার ঘটেছে, যাতে index 0 থেকে শুরু subarray গোনা যায়।
  • for x in nums — array-র উপর একবারই হাঁটি।
  • prefix += x — running total update।
  • count += seen[prefix - k] — prefix - k complement অতীতে যতবার ছিল, ততগুলো বৈধ subarray এখানে শেষ হলো।
  • seen[prefix] += 1 — এখনকার prefix ভবিষ্যতের জন্য টুকে রাখি।

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

[1,1,1] k=2-এ prefix যায় 1,2,3; complement 0 আর 1 অতীতে একবার করে পাওয়া যায় → count 2। [-1,-1,1] k=0-এ prefix যায় -1,-2,-1; শেষ ধাপে prefix-k = -1 আগে একবার দেখা → count 1 ([-1,1])। [3,4,7,2,-3,1,4,2] k=7-এ চারটা subarray শেষ হয় → 4। শেষে print: সব test pass!।

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

সময়

O(n) — array-র উপর এক pass, প্রতি element-এ hash map operation গড়ে O(1)।

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

O(n) — worst case-এ প্রায় সব আলাদা prefix value seen map-এ জমতে পারে।

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

  • seen[0] = 1 initialization ভুলে যাওয়া — তখন একদম শুরু থেকে যোগ হওয়া subarray গোনা বাদ পড়ে।
  • update আর lookup-এর ক্রম উল্টে ফেলা — seen[prefix] += 1 আগে করলে k = 0-এ একই বিন্দু নিজেকে গোনে; সবসময় আগে count += seen[prefix-k], পরে insert।
  • sliding window ব্যবহার করার চেষ্টা — ঋণাত্মক সংখ্যা থাকায় window monotonic নয়, তাই window এখানে কাজ করে না; prefix + hash map লাগবে।

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

ভিত্তির সঙ্গে সম্পর্ক

দুটো ভিত্তি একসাথে: math fundamentals-এর prefix-sum (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/) আর Two Sum (#1)-এর complement lookup। এই note-টা দেখায় কীভাবে দুটো আলাদা chapter-এর idea মিশে একটা medium problem হয়। সম্পূর্ণ চাল ../patterns.md-র Pattern 5-এ।

পরের অনুশীলন

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

Prefix sum + hash map: range-যোগফলের প্রশ্নকে prefix[j] - prefix[i] = k-তে অনুবাদ করো, তারপর প্রতিটা j-তে complement prefix (prefix - k) কতবার দেখেছ তা hash map থেকে গোনো — Two Sum, কিন্তু prefix-এর উপর।

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

ভবিষ্যতের আমাকে: "কতগুলো subarray-র যোগ k" শুনলেই দুই ধাপ — (১) range = prefix[j] - prefix[i], (২) তাই খুঁজছি prefix - k, যা hash map-এ count করা Two Sum। এই note-টা interview-র তিনটা showcase-এর একটা: দুটো chapter-এর সংযোগ এখানে স্পষ্ট দেখানো চাই, আর seen[0]=1-এর কারণ মুখস্থ নয়, বুঝে বলতে পারা চাই।

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