Skip to content

001 — Two Sum

Source

  • Original source: Classic hash map exercise
  • Platform: LeetCode — https://leetcode.com/problems/two-sum/
  • Topic: hash map
  • Difficulty: Easy
  • Pattern: complement lookup
  • Basic idea inherited from: frequency count + complement thinking — যা দেখেছ তা মনে রাখো, তারপর partner query করো

1. Problem in simple words

একটা সংখ্যার array nums আর একটা target দেওয়া আছে। তোমাকে এমন দুটো index ফেরত দিতে হবে যাদের সংখ্যা দুটো যোগ করলে ঠিক target হয়। ধরে নাও উত্তর সবসময় একটাই থাকে, আর একই element দুবার ব্যবহার করা যাবে না।

nums = [2, 7, 11, 15], target = 9
2 + 7 = 9  →  উত্তর index [0, 1]

2. Which basic idea does this inherit from?

এটা দাঁড়িয়ে আছে frequency counting + complement thinking-এর উপর। আগে তুমি এক pass-এ "কী কী দেখেছি" লিখে রাখতে শিখেছ (value → কিছু একটা)। এখানে ঠিক সেই অভ্যাস: প্রতিটা সংখ্যা দেখার সময় তাকে একটা hash map-এ "দেখে ফেলেছি" বলে টুকে রাখো, যাতে পরে তার partner এলে চট করে চিনে ফেলতে পারো। Chapter-এর ../patterns.md-তে এটাই Pattern 2 — complement lookup।

3. What is the hidden math or logic?

লুকানো গণিতটা একদম সরল বীজগণিত: তুমি দুটো সংখ্যা a আর b চাও যেন a + b = target। এর মানে দাঁড়িয়ে থাকা সংখ্যা x হাতে থাকলে তার দরকারি partner একটাই — target - x। একে বলে complement। তাই "জোড়া খুঁজছি" প্রশ্নটা বদলে যায় "এই নির্দিষ্ট complement-টা কি আগে দেখেছি?" প্রশ্নে।

4. Which data structure is needed?

একটা hash map (Python-এ dict), যেটা মনে রাখবে value → index। কারণ আমাদের শুধু "complement আছে কি না" জানলে হবে না, তার index-টাও ফেরত দিতে হবে।

5. Why this data structure fits

Hash map-এ need in seen membership-check গড়ে O(1)। List হলে প্রতিবার partner খুঁজতে পুরো list scan করতে হতো — প্রতি element-এ O(n), মোট O(n^2)। Hash map সেই খোঁজাটাকেই এক লাফে instant করে দেয়, আর সঙ্গে index-ও ধরে রাখে — ঠিক যেটা এই problem-এর দরকার।

6. Real-life analogy

ভাবো তুমি একটা বিয়েবাড়িতে partner খুঁজছ dance-এর জন্য, আর তোমাদের জুড়ির বয়সের যোগফল হতে হবে ঠিক 9। নতুন কেউ ঘরে ঢুকলে তুমি সবার সাথে গিয়ে কথা বলো না — তুমি শুধু মনে করো, "9 পেতে হলে আমার লাগে এই বয়সেরই একজন; আগে কি এমন কাউকে দেখেছি?" তোমার মাথার সেই অতিথি-তালিকাটাই hash map।

7. Visual explanation

nums = [3, 8, 5, 4], target = 9। seen (value → index) ধীরে ধীরে ভরে:

i=0  x=3  need=9-3=6  6 in {}?            না   → seen={3:0}
i=1  x=8  need=9-8=1  1 in {3:0}?         না   → seen={3:0, 8:1}
i=2  x=5  need=9-5=4  4 in {3:0,8:1}?     না   → seen={3:0, 8:1, 5:2}
i=3  x=4  need=9-4=5  5 in seen?          হ্যাঁ → return [seen[5], 3] = [2, 3]

প্রতিবার শুধু পেছনের স্মৃতিতে তাকাচ্ছি — সামনের দিকে কাউকে খুঁজছি না।

8. Example input and output

Input : nums = [2, 7, 11, 15], target = 9    Output: [0, 1]
Input : nums = [3, 2, 4],      target = 6    Output: [1, 2]
Edge  : nums = [3, 3],         target = 6    Output: [0, 1]   (একই value, ভিন্ন index)
Edge  : nums = [1, 5, 3],      target = 100  Output: []       (কোনো জোড়া নেই)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা জোড়া (i, j) ধরে ধরে দেখি যোগফল target কি না।

প্রতিটা i-র জন্য:
    প্রতিটা j > i-র জন্য:
        nums[i] + nums[j] == target হলে return [i, j]

10. Why brute force is slow

দুটো nested loop মানে O(n^2) — array বড় হলে জোড়ার সংখ্যা বর্গাকারে বাড়ে। আসল অপচয়টা হলো: প্রতিটা nums[i]-র জন্য আমরা বাকি পুরো array আবার scan করছি, যদিও আমরা ঠিক জানি কোন একটাই সংখ্যা খুঁজছি (target - nums[i])। জানা জিনিস খুঁজতে scan লাগে না।

11. Key observation

মূল observation: partner-টা অনুমান করতে হয় না, হিসেব করা যায় — সেটা ঠিক target - x। তাই কাজটা "একটা নির্দিষ্ট সংখ্যা আগে এসেছিল কি না" দেখায় নেমে আসে, আর সেটা hash map গড়ে O(1)-এ বলে দেয়।

12. Optimized intuition

Array-র উপর একবারই হাঁটো। প্রতিটা x-এ আগে জিজ্ঞেস করো "আমার complement target - x কি seen-এ আছে?" — থাকলে জোড়া পেয়ে গেছি, দুটো index ফেরত দাও। না থাকলে নিজেকে (x → তার index) seen-এ রেখে এগিয়ে যাও, যাতে ভবিষ্যতের কেউ আমাকে partner হিসেবে পায়। এক pass, O(n)।

13. Thinking tweak

মোচড়: জোড়া খুঁজো না — এ পর্যন্ত কী দেখেছ সেটা মনে রাখো। Brute force সামনের দিকে partner scan করে; এই pattern পেছনের স্মৃতিতে এক ঝলক তাকায়। পুরো hashing chapter-এর প্রাণভোমরা এই একটা tweak।

14. Step-by-step dry run

Input nums = [2, 7, 11, 15], target = 9:

  1. শুরু: seen = {} (খালি)।
  2. i=0, x=2: need = 7; 7 in {}? না → seen = {2: 0}।
  3. i=1, x=7: need = 2; 2 in {2:0}? হ্যাঁ → return [seen[2], 1] = [0, 1]।
  4. শেষ: উত্তর [0, 1]।

15. Python solution

def two_sum(nums, target):
    seen = {}                       # value -> index
    for i, x in enumerate(nums):
        need = target - x           # partner হিসেব করো
        if need in seen:            # অতীত কি partner দিয়েছে?
            return [seen[need], i]
        seen[x] = i                 # নিজেকে ভবিষ্যতের জন্য মনে রাখো
    return []                       # কোনো জোড়া নেই

# ---- tests ----
assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 2, 4], 6) == [1, 2]
assert two_sum([3, 3], 6) == [0, 1]      # একই value, ভিন্ন index
assert two_sum([1, 5, 3], 100) == []     # কোনো জোড়া নেই
print("সব test pass!")

16. Line-by-line code explanation

  • seen = {} — খালি hash map, যেখানে এ পর্যন্ত দেখা প্রতিটা value → তার index জমবে।
  • for i, x in enumerate(nums) — index i আর value x দুটোই একসাথে পাই (index ফেরত দিতে হবে বলে দরকার)।
  • need = target - x — x-এর জন্য দরকারি partner হিসেব করি।
  • if need in seen — সেই partner কি আগেই দেখেছি? dict-এ এই check গড়ে O(1)।
  • return [seen[need], i] — পেলে partner-এর আগের index আর এখনকার index ফেরত দাও।
  • seen[x] = i — না পেলে নিজেকে টুকে রাখো, যাতে পরে কেউ আমাকে partner হিসেবে পায়।

17. Output walkthrough

two_sum([2,7,11,15], 9): i=0 এ 2 যায় seen-এ; i=1 এ x=7, need=2, যেটা seen-এ আছে → return [0, 1]। [3,2,4]-এ জোড়া হয় index 1 ও 2 (2+4=6) → [1, 2]। [3,3]-এ দ্বিতীয় 3-এর complement 3 আগেই দেখা → [0, 1]। [1,5,3]-এ কোনো partner মেলে না → []। শেষে print: সব test pass!।

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

  • seen[x] = i লুকআপের আগে করে ফেলা — তখন target জোড় (যেমন x*2 == target) হলে একই element নিজের সাথে জোড়া বানিয়ে ভুল উত্তর দেয়। সবসময় আগে check, পরে insert।
  • value আর index গুলিয়ে ফেলা — map-এ key হলো value, আর সেটা যে index ফেরত দেয় সেটা মনে রাখা জরুরি।
  • জোড়া না থাকার case ভুলে যাওয়া — loop শেষে [] (বা উপযুক্ত default) ফেরত দিতে হবে।

21. Which basic problem this inherits from

ভিত্তি: এক pass-এ frequency/seen টুকে রাখা (chapter-এর ../concept.md-র counting snippet) + complement thinking। পুরো tweak-এর worked example আছে ../patterns.md-র Pattern 2-তে।

22. Similar harder problems

23. Pattern learned

Complement lookup: partner হিসেব করো (target - x), তারপর "search না করে remember করো" — এক pass, O(1) lookup।

24. Final summary

ভবিষ্যতের আমাকে: "pair / partner / যোগফল target" শুনলেই হাত যাবে hash map-এর দিকে। Partner অনুমান নয়, হিসেব — target - x — আর প্রশ্নটা ঘুরিয়ে দাও "এটা কি আগে দেখেছি?"-তে। এই note-টা চোখ বন্ধ করে লিখতে পারা চাই; পুরো chapter এর উপরই দাঁড়িয়ে।

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