Skip to content

013 — Subarray Sum Equals K

Source

  • Original source: Classic prefix-sum + hash map exercise
  • Platform: LeetCode — https://leetcode.com/problems/subarray-sum-equals-k/
  • Topic: prefix sum + hash map
  • Difficulty: Medium
  • Pattern: prefix sum + hash map
  • Basic idea inherited from: ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/ + Two Sum — prefix value-র উপর করা Two Sum

1. Problem in simple words

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

2. Which basic idea does this inherit from?

এটা দুটো ভিত্তির সংকর। প্রথমটা 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।

3. What is the hidden math or logic?

ধরো 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।

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

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-ও গোনা যায়।

8. Example input and 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

9. Brute force thinking

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

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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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

13. Thinking tweak

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

14. Step-by-step dry run

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

15. Python solution

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

16. Line-by-line code explanation

  • 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 ভবিষ্যতের জন্য টুকে রাখি।

17. Output walkthrough

[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!।

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

  • 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 লাগবে।

21. Which basic problem this inherits from

দুটো ভিত্তি একসাথে: 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-এ।

22. Similar harder problems

23. Pattern learned

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

24. Final summary

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