Skip to content

015 — Subarray Sum Equals K

Source

  • Original source: Classic prefix-sum + hash-map exercise
  • Platform: LeetCode — https://leetcode.com/problems/subarray-sum-equals-k/
  • Topic: array / prefix sums / hash map
  • Difficulty: Medium
  • Pattern: prefix sums + hash map (running prefix-এর complement খোঁজা)
  • Basic idea inherited from: Two Sum-এর complement + prefix sums — "current prefix − k সমান কোনো prefix কি আগে দেখেছি?"

1. Problem in simple words

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

nums = [1, 1, 1], k = 2
sum 2 হয়: [1,1] (index 0-1) আর [1,1] (index 1-2)  ->  count = 2

2. Which basic idea does this inherit from?

এটা Two Sum-এর complement thinking আর prefix sums মিলিয়ে দেয়। prefix sum-এ sum(i..j) = prefix[j] - prefix[i-1]; তাই sum = k মানে prefix[i-1] = prefix[j] - k। অর্থাৎ চলতে চলতে প্রশ্ন করো — "current prefix − k সমান কোনো prefix কি আগে দেখেছি?" — ঠিক Two Sum-এর "complement আগে দেখেছি?" এর মতো। গভীরভাবে ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/।

3. What is the hidden math or logic?

লুকানো logic: একটা subarray (i..j)-এর sum হলো prefix[j] - prefix[i-1]। সেটা k হওয়া মানে prefix[i-1] = prefix[j] - k। তাই প্রতিটা j-তে দরকার "এর আগে কতবার prefix[j] - k মান-এর prefix দেখা গেছে" — প্রতিটা এমন পুরনো prefix একটা valid subarray-র শুরু। count জমিয়ে রাখা prefix-এর frequency map থেকে আসে।

4. Which data structure is needed?

একটা hash map (dict) seen, যেখানে key = এ পর্যন্ত দেখা prefix sum, value = সেটা কতবার এসেছে। সাথে দুটো scalar — running (চলমান prefix sum) আর count। শুরুতে seen = {0: 1} (খালি prefix একবার ধরা)।

5. Why this data structure fits

Dict-এর lookup/insert average O(1), তাই "এই prefix কতবার আগে দেখেছি" এক pass-এ জানা যায়। prefix sum negative-ও হতে পারে বলে fixed-size array না নিয়ে dict নেওয়াই সঠিক। এক pass-এ পুরো count হয়ে যায়।

6. Real-life analogy

ভাবো তুমি হাঁটতে হাঁটতে "শুরু থেকে এ পর্যন্ত মোট কত" টুকছ। কেউ যদি জানতে চায় "ঠিক k দূরত্বের কয়টা টুকরো আছে", তুমি প্রতি জায়গায় ভাবো — "এর k আগে আমি যে মোট-মান-এ ছিলাম, সেটা ক'বার ছুঁয়েছি?" প্রতিটা সেই পুরনো মুহূর্ত একটা ঠিক-k টুকরোর শুরু।

7. Visual explanation

nums = [1, 2, 1], k = 3 দিয়ে (patterns.md-র উদাহরণ):

seen = {0:1}
x=1: running=1; need 1-3=-2 (নেই); seen={0:1, 1:1}
x=2: running=3; need 3-3=0 (আছে 1 বার!) count=1; seen={0:1,1:1,3:1}
x=1: running=4; need 4-3=1 (আছে 1 বার!) count=2; seen={...,4:1}
answer: 2   -> subarray [1,2] আর [2,1]

8. Example input and output

Input : [1, 1, 1], k=2 -> 2
Input : [1, 2, 3], k=3 -> 2   ([1,2] আর [3])

Edge case 1 (negative + 0): [1, -1, 0], k=0 -> 3  ([1,-1], [0], [1,-1,0])
Edge case 2 (লম্বা mix): [3,4,7,2,-3,1,4,2], k=7 -> 4

9. Brute force thinking

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

count = 0
for i in range(n):
    s = 0
    for j in range(i, n):
        s += nums[j]
        if s == k: count += 1

10. Why brute force is slow

দুটো nested loop মানে O(n^2)। বারবার overlap যোগ হচ্ছে — i fix রেখে j বাড়ালে যে কাজ, পরের i-তে আবার পুনরাবৃত্তি। অথচ prefix sum আর complement-map দিয়ে এক pass-এই সব subarray গোনা যায়।

11. Key observation

মূল observation: sum(i..j) = k ঘটনাটাকে prefix-এর ভাষায় লেখা যায় — prefix[j] - prefix[i-1] = k, অর্থাৎ prefix[i-1] = prefix[j] - k। তাই সব জোড়া না দেখে, প্রতিটা j-তে শুধু "আগে কতবার prefix[j]-k দেখেছি" জানলেই count হয়ে যায়।

12. Optimized intuition

seen = {0: 1} দিয়ে শুরু করো (যাতে শুরু থেকেই k হওয়া subarray গোনা যায়)। বাঁ থেকে ডানে হাঁটো; প্রতিটা x-এ running += x, তারপর count += seen.get(running - k, 0) (এই prefix কতবার দরকারি complement-রূপে আগে এসেছে), শেষে seen[running] এক বাড়াও। এক pass, O(n)।

13. Thinking tweak

মোচড়: "সব subarray-র sum মিলাব" (O(n^2)) ভুলে গিয়ে ভাবো "prefix sum-এর complement (running − k) আগে কতবার দেখেছি গুনব।" Two Sum-এর complement trick-ই, শুধু value-র জায়গায় prefix sum।

14. Step-by-step dry run

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

  1. seen={0:1}, running=0, count=0।
  2. x=1: running=1; need 1-3=-2 (নেই, +0); seen={0:1, 1:1}।
  3. x=2: running=3; need 3-3=0 (আছে 1 বার) → count=1; seen={0:1,1:1,3:1}।
  4. x=3: running=6; need 6-3=3 (আছে 1 বার) → count=2; seen={...,6:1}।
  5. ফল: count = 2 (subarray [1,2] আর [3])।

15. Python solution

def subarray_sum(nums, k):
    count = 0
    running = 0
    seen = {0: 1}                            # prefix sum -> কতবার দেখা গেছে
    for x in nums:
        running += x
        count += seen.get(running - k, 0)    # আগে running-k দেখেছি?
        seen[running] = seen.get(running, 0) + 1
    return count

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

16. Line-by-line code explanation

  • seen = {0: 1} — খালি prefix একবার ধরা; এতে শুরু থেকেই k হওয়া subarray গোনা যায়।
  • running += x — চলমান prefix sum update।
  • count += seen.get(running - k, 0) — এই point-এ শেষ হওয়া কয়টা subarray-র sum ঠিক k; প্রতিটা পুরনো running-k prefix একটা subarray।
  • seen[running] = seen.get(running, 0) + 1 — এখনকার prefix-এর frequency বাড়াও (পরের জন্য)।
  • lookup-টা insert-এর আগে — যাতে দৈর্ঘ্য-0 subarray ভুল করে না গোনা হয়।

17. Output walkthrough

[1,1,1], k=2 → prefix 0,1,2,3; complement মিলে 2 বার → 2, assert pass। [1,2,3], k=3 → 2; [1,-1,0], k=0 → [1,-1], [0], [1,-1,0] মিলে 3; [3,4,7,2,-3,1,4,2], k=7 → 4। শেষে print: সব test pass!।

18. Time complexity

O(n) — এক pass; প্রতিটা element-এ একবার O(1) lookup আর একবার O(1) insert।

19. Space complexity

O(n) — সবচেয়ে খারাপ ক্ষেত্রে প্রায় সব prefix sum আলাদা হয়ে dict-এ জমা হতে পারে।

20. Common mistakes

  • seen = {0: 1} শুরু না করা — তখন শুরু থেকেই (prefix == k) হওয়া subarray গুলো বাদ পড়ে।
  • insert আগে করে তারপর lookup — তখন current prefix নিজেকেই complement বানিয়ে দৈর্ঘ্য-0 subarray গোনে; lookup আগে, insert পরে।
  • শুধু sorted/positive ভেবে sliding window লাগানো — negative থাকলে window monotonic নয়, তাই prefix + hash map-ই সঠিক।

21. Which basic problem this inherits from

ভিত্তি: Two Sum-এর complement lookup (#2) + prefix sums (Static Range Sum #9)। দুটোই "দরকারি জিনিস আগে দেখেছি কিনা" hash map-এ মেলায়। chapter-এর ../patterns.md-এর "Pattern 3 — Prefix Sums" দেখো।

22. Similar harder problems

23. Pattern learned

Prefix sums + hash map: "count subarrays summing to K" (negative-সহ) দেখলে চলমান prefix রাখো আর "running − k আগে কতবার দেখেছি" গুনো। Two Sum-এর complement trick prefix sum-এ বসানো — O(n)।

24. Final summary

ভবিষ্যতের আমাকে: "count += seen[running − k]; seen শুরু হয় {0:1} দিয়ে; lookup আগে, insert পরে।" "subarray sum equals K (negative থাকতে পারে)" দেখলেই prefix + hash map মনে করবে — O(n) time।

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