Skip to content

014 — Continuous Subarray Sum

Source

  • Original source: Classic prefix-mod + hash map exercise
  • Platform: LeetCode — https://leetcode.com/problems/continuous-subarray-sum/
  • Topic: prefix sum + hash map (mod)
  • Difficulty: Medium
  • Pattern: prefix sum + hash map (mod)
  • Basic idea inherited from: Subarray Sum Equals K — prefix-এর বদলে remainder জমা রাখো

1. Problem in simple words

একটা অঋণাত্মক সংখ্যার array nums আর একটা সংখ্যা k দেওয়া আছে। বলতে হবে: এমন কোনো contiguous subarray আছে কি, যার দৈর্ঘ্য অন্তত 2 আর যোগফল k-এর একটা গুণিতক (অর্থাৎ 0, k, 2k, 3k, ...)? উত্তর True/False।

nums = [23, 2, 4, 6, 7], k = 6
[2, 4]-এর যোগ 6 = 6 × 1 → হ্যাঁ
উত্তর: True

2. Which basic idea does this inherit from?

এটা সরাসরি Subarray Sum Equals K (#13)-এর ভাই। সেখানে আমরা prefix value জমা রাখতাম; এখানে শুধু একটা মোচড় — prefix-এর বদলে prefix % k (remainder) জমা রাখি। ভিত্তি একই prefix-sum + hash map (Pattern 5), নতুন উপাদান modular arithmetic।

3. What is the hidden math or logic?

মূল সংখ্যাতত্ত্ব: যদি দুটো prefix-এর k দিয়ে ভাগশেষ (remainder) এক হয়, তাহলে তাদের বিয়োগফল k-এর গুণিতক। কারণ prefix[j] ≡ prefix[i] (mod k) মানে prefix[j] - prefix[i] ≡ 0 (mod k), আর সেই বিয়োগফলই হলো (i, j] subarray-র যোগফল। তাই "k-এর গুণিতক যোগফল আছে?" প্রশ্ন বদলে যায় "একই remainder কি আগে দেখেছি?" প্রশ্নে।

4. Which data structure is needed?

একটা hash map (remainder → সেই remainder প্রথম যে index-এ দেখা)। count নয়, আমরা প্রথম index রাখি, কারণ দৈর্ঘ্য অন্তত 2 হতে হবে — বর্তমান index থেকে সেই প্রথম দেখা index-এর দূরত্ব মাপতে হবে।

5. Why this data structure fits

আমরা প্রতিটা index-এ জিজ্ঞেস করি "এই remainder কি আগে দেখেছি, আর দূরত্ব ≥ 2?" hash map এই lookup O(1)-এ দেয়। আর প্রথম-দেখা index রাখলে দূরত্ব সবচেয়ে বড় হয়, তাই length ≥ 2 শর্ত মেলার সম্ভাবনাও সর্বোচ্চ থাকে। তাই একই remainder পরে আবার এলে map overwrite করি না।

6. Real-life analogy

ভাবো একটা গোল ঘড়ির ডায়াল, ঘর সংখ্যা k। তুমি হাঁটছ আর প্রতিটা ধাপে কাঁটা কিছু ঘর এগোচ্ছে। যখনই কাঁটা আগের কোনো ঘরে ফিরে আসে, বোঝো এর মাঝে তুমি পূর্ণ পাক (k-এর গুণিতক) হেঁটেছ। প্রথমবার কোন ঘরে ছিলে তা মনে রাখলে বুঝতে পারো ফিরে আসতে অন্তত দুই ধাপ লেগেছে কি না।

7. Visual explanation

nums = [23, 2, 4, 6, 7], k = 6। seen রাখে remainder → প্রথম index; শুরুতে {0: -1}:

শুরু: prefix=0, seen={0:-1}
i=0 x=23: prefix=23, r=23%6=5, নতুন → seen={0:-1, 5:0}
i=1 x=2 : prefix=25, r=25%6=1, নতুন → seen={0:-1, 5:0, 1:1}
i=2 x=4 : prefix=29, r=29%6=5, আগে index 0! দূরত্ব 2-0=2 ≥ 2 → True

r=5 আগে index 0-এ দেখা, এখন index 2 — মাঝের [2,4] যোগফল 6, যা 6-এর গুণিতক।

8. Example input and output

Input : [23, 2, 4, 6, 7], k = 6     Output: True    ([2,4] = 6)
Input : [23, 2, 6, 4, 7], k = 6     Output: True    (পুরোটা 42 = 6×7)
Input : [23, 2, 6, 4, 7], k = 13    Output: False
Edge  : [0, 0], k = 1               Output: True    ([0,0] = 0 = 0×1)
Edge  : [1, 0], k = 2               Output: False   (length-2 যোগ 1, গুণিতক নয়)

9. Brute force thinking

প্রথম সরল চিন্তা: দৈর্ঘ্য ≥ 2 প্রতিটা subarray ধরে যোগফল বের করো, দেখো k-এর গুণিতক কি না।

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

10. Why brute force is slow

দুটো nested loop মানে O(n^2)। আবারও সেই অপচয়: প্রতিটা শুরু-বিন্দুর জন্য বারবার একই অঞ্চলের যোগফল নতুন করে গোনা। অথচ remainder-এর পুনরাবৃত্তি একবার hash map-এ রাখলেই "k-এর গুণিতক যোগফল আছে?" এক pass-এ বলা যায়।

11. Key observation

মূল observation: k-এর গুণিতক যোগফল ⇔ দুই প্রান্তের prefix-এর remainder সমান। তাই আসল subarray যোগফল হিসেব করারও দরকার নেই — শুধু running prefix-এর remainder চিনে রাখলেই হয়, আর "একই remainder আগে দেখেছি কি (≥ 2 দূরে)?" — এটাই উত্তর।

12. Optimized intuition

seen = {0: -1} দিয়ে শুরু করো (index -1 ধরে নিলে শুরু থেকে শুরু হওয়া subarray-ও দৈর্ঘ্য সঠিক পায়)। running prefix রাখো, প্রতিবার r = prefix % k। r আগে দেখা থাকলে আর দূরত্ব ≥ 2 হলে True; আগে না দেখা থাকলে প্রথমবারের index লিখে রাখো (পরে overwrite নয়)। শেষ পর্যন্ত না মিললে False। O(n)।

13. Thinking tweak

মোচড়: যখন প্রশ্ন "গুণিতক/divisible", তখন prefix-এর জায়গায় prefix % k জমাও — সমান remainder মানেই গুণিতক ব্যবধান। Subarray Sum Equals K-এর hash map চালটাই, শুধু key হিসেবে value নয়, value-র remainder। ছোট মোচড়, কিন্তু পুরো divisibility-পরিবার এতেই খোলে।

14. Step-by-step dry run

Input nums = [23, 2, 6, 4, 7], k = 6:

  1. শুরু: prefix = 0, seen = {0: -1}।
  2. i=0, x=23: prefix=23, r=5, নতুন → seen={0:-1, 5:0}।
  3. i=1, x=2: prefix=25, r=1, নতুন → seen={0:-1, 5:0, 1:1}।
  4. i=2, x=6: prefix=31, r=1, আগে index 1, দূরত্ব 2-1=1 < 2 → না (এবং overwrite নয়)।
  5. i=3, x=4: prefix=35, r=5, আগে index 0, দূরত্ব 3-0=3 ≥ 2 → True।

15. Python solution

def check_subarray_sum(nums, k):
    seen = {0: -1}                     # remainder -> প্রথম যেখানে দেখা
    prefix = 0
    for i, x in enumerate(nums):
        prefix += x
        r = prefix % k                 # mod দিয়ে partner খুঁজি
        if r in seen:
            if i - seen[r] >= 2:       # length >= 2 চাই
                return True
        else:
            seen[r] = i                # শুধু প্রথমবার লিখি
    return False

# ---- tests ----
assert check_subarray_sum([23, 2, 4, 6, 7], 6) == True
assert check_subarray_sum([23, 2, 6, 4, 7], 6) == True
assert check_subarray_sum([23, 2, 6, 4, 7], 13) == False
assert check_subarray_sum([0, 0], 1) == True
assert check_subarray_sum([1, 0], 2) == False
print("সব test pass!")

16. Line-by-line code explanation

  • seen = {0: -1} — খালি prefix-এর remainder 0, index -1 ধরে, যাতে শুরু থেকে subarray-ও দৈর্ঘ্য ঠিক পায়।
  • for i, x in enumerate(nums) — index ও value দুটোই লাগে (দূরত্ব মাপতে index)।
  • prefix += x — running যোগফল।
  • r = prefix % k — এই বিন্দুর remainder।
  • if r in seen: if i - seen[r] >= 2: return True — একই remainder আগে দেখা, আর যথেষ্ট দূরে → গুণিতক subarray পেলাম।
  • else: seen[r] = i — নতুন remainder হলে শুধু প্রথম index রাখি (দূরত্ব সর্বোচ্চ রাখতে overwrite করি না)।

17. Output walkthrough

[23,2,4,6,7] k=6-এ remainder 5 আবার আসে index 2-এ (আগে 0), দূরত্ব 2 → True। [23,2,6,4,7] k=6-এ remainder 5 আবার আসে index 3-এ (আগে 0), দূরত্ব 3 → True। একই array k=13-এ কোনো remainder ≥ 2 দূরত্বে পুনরাবৃত্তি হয় না → False। [0,0] k=1-এ remainder 0 index 1-এ (আগে -1), দূরত্ব 2 → True। শেষে print: সব test pass!।

18. Time complexity

O(n) — array-র উপর এক pass, প্রতি element-এ একটা mod আর hash map operation, সবই গড়ে O(1)।

19. Space complexity

O(min(n, k)) — map-এ আলাদা remainder জমে, যা k-টার বেশি হতে পারে না (এবং n-এর বেশিও নয়)।

20. Common mistakes

  • count রেখে ফেলা (Subarray Sum Equals K-এর মতো) — এখানে দরকার প্রথম index, যাতে length ≥ 2 যাচাই হয়।
  • একই remainder এলে index overwrite করা — তাতে দূরত্ব ছোট হয়ে valid উত্তর মিস হতে পারে; শুধু প্রথমবার লেখো।
  • length ≥ 2 শর্ত ভুলে যাওয়া — তখন একক element-ও (বা শূন্য-দৈর্ঘ্য) ভুলভাবে True দেবে।
  • seen = {0: -1} initialization বাদ দেওয়া — শুরু থেকে শুরু হওয়া গুণিতক subarray মিস হবে।

21. Which basic problem this inherits from

ভিত্তি: Subarray Sum Equals K (#13)-এর prefix-sum + hash map, যা নিজে Two Sum + math fundamentals-এর prefix idea-র সংকর। নতুন উপাদান modular arithmetic — key হিসেবে prefix % k। সম্পূর্ণ চাল ../patterns.md-র Pattern 5-এ।

22. Similar harder problems

23. Pattern learned

Prefix sum + hash map (mod): divisibility-র প্রশ্নে prefix-এর বদলে prefix % k জমাও; সমান remainder মানেই দুই বিন্দুর মধ্যে k-এর গুণিতক যোগফল। প্রথম-দেখা index রাখলে length শর্তও যাচাই করা যায়।

24. Final summary

ভবিষ্যতের আমাকে: "k-এর গুণিতক যোগফলওয়ালা subarray" শুনলেই prefix % k আর "একই remainder আগে দেখেছি?" মনে পড়বে। দুটো জিনিস ভুলব না — (১) count নয়, প্রথম index রাখা, (২) {0:-1} initialization। এটা #13-এর উপর মাত্র এক লাইন মোচড়, কিন্তু modular চিন্তাটা না বুঝলে ফাঁদে পড়া সহজ।

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