Problem link ও উৎস
- **Original source:** Classic hash-map exercise
- **Platform:** LeetCode —
- **Topic:** array / hash map
- **Difficulty:** Easy
- **Pattern:** frequency / complement lookup (hash map)
- **Basic idea inherited from:** Math level 5 (prefix/contribution)-এর complement thinking — "যা দরকার সেটা আগে দেখেছি কিনা" খোঁজা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array `nums` আর একটা `target` দেওয়া আছে। এমন **দুটো index** খুঁজে বের করো যাদের value যোগ করলে ঠিক `target` হয়। ধরে নাও ঠিক একটা উত্তর আছে, আর একই element দুবার ব্যবহার করা যাবে না। দুটো index ফেরত দাও।
যেমন `nums = [2, 7, 11, 15]`, `target = 9` হলে `2 + 7 = 9`। তাই উত্তর **indices `[0, 1]`**; value `[2, 7]` ফেরত দিতে বলা হয়নি।
### Input ও output {#8-example-input-and-output}
| nums | target | উত্তর: দুটি index | মিলিয়ে দেখো |
| --- | --- | --- | --- |
| `[2, 7, 11, 15]` | 9 | `[0, 1]` | `nums[0] + nums[1] = 2 + 7` |
| `[3, 2, 4]` | 6 | `[1, 2]` | `nums[1] + nums[2] = 2 + 4` |
| `[3, 3]` | 6 | `[0, 1]` | মান সমান, কিন্তু দুটি আলাদা index |
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি দোকানে দাঁড়িয়ে, হাতে 9 টাকা। প্রতিটা জিনিসের দাম দেখে ভাবছ — "এটা কিনলে আর কত টাকার জিনিস লাগবে?" সেই বাকি টাকার জিনিস তুমি একটা মনে-রাখা list-এ আগে দেখেছ কিনা চট করে মিলিয়ে নাও। list-টাই hash map।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা math chapter-এর **complement thinking** reuse করে: প্রতিটা x-এর জন্য আমার দরকার তার "জোড়া" `target - x`। পুরো array জুড়ে সব pair না মিলিয়ে, প্রশ্নটা উল্টে দাও — "এই complement টা কি আগে কোথাও দেখেছি?" এই "আগে দেখেছি কিনা" idea-র গভীর রূপ [../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)-তে (subarray sum K-এও একই trick)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: `a + b = target` সমীকরণটা একটা variable-এর হয়ে যায় — `b = target - a`। তাই প্রতিটা element-কে আলাদা করে অন্য সবার সাথে না মিলিয়ে, শুধু তার একমাত্র দরকারি জোড়া `target - a` খুঁজলেই হয়। আর সেই খোঁজা O(1)-এ করতে hash map।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash map (dict)**, যেখানে key = এ পর্যন্ত দেখা value, আর value = সেই value-র index। এতে "complement কি আগে দেখেছি?" প্রশ্নের উত্তর average O(1)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Hash map-এর membership/lookup average **O(1)** — concept.md বলেছে unsorted array-তে "এই value আছে কিনা" খোঁজা O(n), কিন্তু dict-এ O(1)। প্রতিটা element-এ আমরা একবার lookup করি (complement আছে?) আর একবার insert করি (নিজেকে রাখি) — দুটোই O(1), তাই পুরোটা O(n)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা জোড়া `(i, j)` ধরে দেখি যোগফল `target` হয় কিনা — দুটো nested loop।
```text
for i in range(n):
for j in range(i+1, n):
if nums[i] + nums[j] == target:
return [i, j]
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop মানে প্রায় `n*(n-1)/2` জোড়া পরীক্ষা — **O(n^2)**। array বড় হলে এটা ভয়ংকর ধীর। বারবার একই কাজ হচ্ছে: প্রতিটা element-এর জন্য বাকি পুরো array আবার scan করছি, অথচ আগে দেখা value গুলো মনে রাখলেই হতো।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একটা element fix করলে, তার জোড়া **একদমই নির্দিষ্ট** — `target - x`, আর কিছু না। তাই সব জোড়া try করার দরকার নেই; শুধু এই একটাই দরকারি সংখ্যা আগে দেখেছি কিনা দেখলেই হয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একবারই বাঁ থেকে ডানে হাঁটো। প্রতিটা `x`-এ আগে জিজ্ঞাসা করো "`target - x` কি আগের কোনো index-এ দেখেছি?" — দেখে থাকলে জোড়া পেয়ে গেলে। না দেখলে `x`-কে তার index সহ dict-এ রেখে এগিয়ে যাও। এক pass, O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব জোড়া মেলাব" (O(n^2)) বদলে "প্রতিটা সংখ্যার একমাত্র দরকারি সঙ্গী আগে দেখেছি কিনা মনে রাখব" (O(n))। মনে-রাখাটাই hash map।
### ছবিতে বোঝা {#7-visual-explanation}
বর্তমান মান `x` হলে তার জোড়া `need = target - x`। রঙ করা বাক্সগুলোতে দেখো কীভাবে আগের index-এর সঙ্গে বর্তমানটি মেলে।
```dsa
kind: array
title: "target 9: আগে দেখা 2-এর সঙ্গে নতুন 7 মেলে"
steps:
- label: "১ · index 0-তে 2 পড়ি"
values: [2, 7, 11, 15]
active: [0]
pointers: {i: 0}
note: "need = 7। আগে কোনো মান দেখা হয়নি; তাই seen-এ 2 → 0 রাখি।"
- label: "২ · index 1-তে 7 পড়ি"
values: [2, 7, 11, 15]
active: [0, 1]
pointers: {জোড়া: 0, i: 1}
note: "need = 2। seen জানায় 2 আছে index 0-তে। উত্তর [0, 1]; এখানেই থামি।"
```
| i | x | need | খোঁজার আগে seen: value → index | সিদ্ধান্ত |
| --- | --- | --- | --- | --- |
| 0 | 2 | 7 | `{}` | 7 নেই; `2 → 0` রাখো |
| 1 | 7 | 2 | `{2: 0}` | 2 আছে; `[0, 1]` ফেরত দাও |
`seen`-এ **আগের** index-গুলোই থাকে। তাই পাওয়া জোড়ায় একই element দুবার ব্যবহৃত হয় না।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums = [3, 2, 4]`, `target = 6`:
1. শুরু: `seen = {}`।
2. `i=0, x=3`: need `6-3=3`; `seen`-এ নেই → `seen = {3:0}`।
3. `i=1, x=2`: need `6-2=4`; `seen`-এ নেই → `seen = {3:0, 2:1}`।
4. `i=2, x=4`: need `6-4=2`; `seen`-এ আছে (2 → index 1) → return `[1, 2]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
need = target - x
if need in seen: # complement আগে দেখেছি?
return [seen[need], i]
seen[x] = i # নিজেকে রেখে এগোও
return [] # (problem বলে উত্তর সবসময় আছে)
# ---- 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]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `seen = {}` — এ পর্যন্ত দেখা value→index রাখার dict।
- `for i, x in enumerate(nums)` — index আর value একসাথে নিয়ে একবার হাঁটা।
- `need = target - x` — এই x-এর একমাত্র দরকারি জোড়া।
- `if need in seen` — সেই জোড়া আগে দেখেছি কিনা, O(1) check।
- `return [seen[need], i]` — আগের index আগে, এখনকার index পরে।
- `seen[x] = i` — না মিললে নিজেকে future-এর জন্য রেখে যাও।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[2,7,11,15], 9`: x=2 রাখা হয়, x=7-এ need=2 dict-এ পাওয়া যায় → `[0,1]`, assert pass। `[3,2,4], 6` দেয় `[1,2]`; `[3,3], 6`-এ প্রথম 3 রাখা হয়, দ্বিতীয় 3-এ need=3 পাওয়া যায় → `[0,1]`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
complement lookup — JS-এ `Map` দিয়ে value→index রাখি; আগে খোঁজো, পরে নিজেকে রাখো।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function twoSum(nums, target) {
const seen = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i]; // complement আগে দেখেছি?
seen.set(nums[i], i); // না হলে নিজেকে রেখে এগোও
}
return []; // (problem বলে উত্তর সবসময় আছে)
}
// ---- test cases (file-এর example + edge case) ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(twoSum([2, 7, 11, 15], 9), [0, 1]), "2+7");
assert(eq(twoSum([3, 2, 4], 6), [1, 2]), "2+4");
assert(eq(twoSum([3, 3], 6), [0, 1]), "duplicate 3+3");
assert(eq(twoSum([-1, -2, -3, -4, -5], -8), [2, 4]), "negative");
console.log("সব JS test pass!");
```
> **JS টীকা:** numeric key নিরাপদ রাখতে `Map` (plain object `{}`-এ key string হয়ে যায়, negative/বড় সংখ্যায় বিভ্রান্তি)। ক্রম জরুরি — আগে `has(need)`, পরে `set`; উল্টালে `target = 2*x` হলে একই element-কে নিজের জোড়া বানিয়ে ফেলবে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function twoSum(nums: number[], target: number): number[] {
const seen = new Map