Problem link ও উৎস
- **Original source:** Classic hash map exercise
- **Platform:** LeetCode —
- **Topic:** hash map
- **Difficulty:** Easy
- **Pattern:** complement lookup
- **Basic idea inherited from:** frequency count + complement thinking — যা দেখেছ তা মনে রাখো, তারপর partner query করো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার array `nums` আর একটা `target` দেওয়া আছে। তোমাকে এমন **দুটো index** ফেরত দিতে হবে যাদের সংখ্যা দুটো যোগ করলে ঠিক `target` হয়। ধরে নাও উত্তর সবসময় একটাই থাকে, আর একই element দুবার ব্যবহার করা যাবে না।
```text
nums = [2, 7, 11, 15], target = 9
2 + 7 = 9 → উত্তর index [0, 1]
```
### Input ও output {#8-example-input-and-output}
```text
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: [] (কোনো জোড়া নেই)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা বিয়েবাড়িতে partner খুঁজছ dance-এর জন্য, আর তোমাদের জুড়ির বয়সের যোগফল হতে হবে ঠিক 9। নতুন কেউ ঘরে ঢুকলে তুমি সবার সাথে গিয়ে কথা বলো না — তুমি শুধু মনে করো, "9 পেতে হলে আমার লাগে এই বয়সেরই একজন; আগে কি এমন কাউকে দেখেছি?" তোমার মাথার সেই অতিথি-তালিকাটাই hash map।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **frequency counting + complement thinking**-এর উপর। আগে তুমি এক pass-এ "কী কী দেখেছি" লিখে রাখতে শিখেছ (`value → কিছু একটা`)। এখানে ঠিক সেই অভ্যাস: প্রতিটা সংখ্যা দেখার সময় তাকে একটা hash map-এ "দেখে ফেলেছি" বলে টুকে রাখো, যাতে পরে তার partner এলে চট করে চিনে ফেলতে পারো। Chapter-এর [../patterns.md](../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-এর দরকার।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা জোড়া (i, j) ধরে ধরে দেখি যোগফল target কি না।
```text
প্রতিটা 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।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [3, 8, 5, 4]`, `target = 9`। `seen` (value → index) ধীরে ধীরে ভরে:
```text
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-এ ধাপে ধাপে {#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]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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 হিসেবে পায়।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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) ফেরত দিতে হবে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: এক pass-এ frequency/seen টুকে রাখা (chapter-এর [../concept.md](../concept.md)-র counting snippet) + complement thinking। পুরো tweak-এর worked example আছে [../patterns.md](../patterns.md)-র Pattern 2-তে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Two Sum II - Input Array Is Sorted —