কনটেন্টে যান

001 — Two Sum

Problem link ও উৎস

  • 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 করো

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

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

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

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

Input ও 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: []       (কোনো জোড়া নেই)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ছবিতে বোঝা

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]

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

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

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

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

Python

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

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

  • 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 হিসেবে পায়।

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

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

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

সময়

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

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

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

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

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

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

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

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

পরের অনুশীলন

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

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

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

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

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