Problem link ও উৎস
- **Original source:** Classic hash set exercise
- **Platform:** LeetCode —
- **Topic:** hash set
- **Difficulty:** Easy
- **Pattern:** seen-set
- **Basic idea inherited from:** set algebra ([../operations.md](../operations.md)) — intersection, union, difference
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো array `nums1` আর `nums2` দেওয়া আছে। তোমাকে এমন সব সংখ্যা ফেরত দিতে হবে যেগুলো **দুটো array-তেই** আছে। উত্তরে প্রতিটা সংখ্যা **একবারই** থাকবে (distinct), ক্রম যেকোনো।
```text
nums1 = [1, 2, 2, 1], nums2 = [2, 2] → [2]
nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4] → [4, 9] (যেকোনো ক্রমে)
```
### Input ও output {#8-example-input-and-output}
```text
Input : nums1 = [1, 2, 2, 1], nums2 = [2, 2] Output: [2]
Input : nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4] Output: [4, 9] (যেকোনো ক্রমে)
Input : nums1 = [1, 2, 3], nums2 = [4, 5, 6] Output: [] (common নেই)
Edge : nums1 = [], nums2 = [1, 2] Output: [] (একটা খালি)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুই বন্ধুর Spotify playlist মেলানোর কথা ভাবো — তোমরা জানতে চাও কোন গানগুলো **দুজনেরই** আছে। তুমি এক বন্ধুর গানের নাম মাথায় তুলে নাও (set), তারপর অন্য বন্ধুর playlist-এর প্রতিটা গান নিয়ে দেখো "এটা কি আমার তালিকায় আছে?" মিললে common। দুজনের কারো playlist-এ একই গান দুবার থাকলেও common list-এ একবারই লেখো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **set algebra**-র উপর — [../operations.md](../operations.md)-এ দেখা `a & b` (intersection), `a | b` (union), `a - b` (difference)। মূল চিন্তাটা **seen-set** (Pattern 4)-এরই রূপ: এক array-কে স্মৃতিতে (set-এ) তুলে রেখে, অন্য array-র প্রতিটা element সেখানে আছে কি না দেখা — "আগে দেখেছি?" প্রশ্নটাই।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো গণিতটা আক্ষরিক **set intersection**: দুই set-এর common element। duplicate গুরুত্বহীন বলে আগে দুই array-কে set বানিয়ে নিলে (১) duplicate আপনাআপনি মুছে যায়, (২) "দুই দিকে আছে কি" প্রশ্নটা O(1) membership-এ নেমে আসে। ফল: distinct common elements।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash set** (Python-এ `set`)। দুই array-র অন্তত একটাকে set-এ তুলি (দ্রুত membership-এর জন্য), আর উত্তরও একটা set-এ জমাই (distinct রাখতে)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Set-এ `x in first` membership গড়ে **O(1)**, আর set নিজে থেকেই duplicate ফেলে দেয় — দুটোই এই problem-এর সরাসরি চাহিদা। Nested-loop দিয়ে common খুঁজলে হতো O(n*m); set সেটাকে O(n+m)-এ নামায়, আর distinct-ও ফ্রি-তে দেয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: `nums1`-এর প্রতিটা element `nums2`-তে আছে কি না খুঁজে দেখি, থাকলে উত্তরে রাখি (আর duplicate এড়াতে আগে রেখেছি কি না দেখি)।
```text
result = []
nums1-এর প্রতিটা x:
x যদি nums2-তে থাকে এবং result-এ না থাকে:
result-এ x যোগ করো
return result
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
`x in nums2` প্রতিবার O(m), আর `nums1`-এর প্রতিটা element-এর জন্য সেটা = মোট **O(n*m)**। উপরন্তু `x in result` check-ও list-এ O(k)। অথচ set membership O(1), তাই বারবার পুরো array scan করাটাই অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **duplicate উত্তরের কোনো মানে রাখে না, আর "common কি না" = membership প্রশ্ন**। দুই কথা মিলিয়ে দেখায় — set-ই নিখুঁত হাতিয়ার: membership O(1), আর distinct আপনাআপনি।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`nums1`-কে একটা set `first`-এ তোলো। তারপর `nums2`-র প্রতিটা element নিয়ে দেখো সে `first`-এ আছে কি না — থাকলে একটা `result` set-এ যোগ করো (set নিজেই duplicate সামলায়)। শেষে `result`-কে list করে ফেরত দাও। সব O(n+m)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "দুই array মেলাও" না ভেবে ভাবো "এক array-কে স্মৃতিতে তুলে রাখো, অন্যটায় membership জিজ্ঞেস করো।" এটাই seen-set; আর Python-এ পুরোটা এক লাইনে: `set(nums1) & set(nums2)`।
### ছবিতে বোঝা {#7-visual-explanation}
`nums1 = [4, 9, 5]`, `nums2 = [9, 4, 9, 8, 4]`:
```text
first = set(nums1) = {4, 9, 5} (nums1-কে স্মৃতিতে তুললাম)
nums2 ঘুরে দেখি:
9 in first? হ্যাঁ → result={9}
4 in first? হ্যাঁ → result={9, 4}
9 in first? হ্যাঁ → result={9, 4} (set duplicate রাখে না)
8 in first? না → result={9, 4}
4 in first? হ্যাঁ → result={9, 4}
result = {4, 9} → list করে ফেরত
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums1 = [1, 2, 2, 1]`, `nums2 = [2, 2]`:
1. `first = set(nums1)` = `{1, 2}`।
2. `result = set()`।
3. `nums2`: `2 in first?` হ্যাঁ → `result = {2}`; পরের `2 in first?` হ্যাঁ → `result = {2}` (অপরিবর্তিত)।
4. `list(result)` = `[2]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def intersection(nums1, nums2):
first = set(nums1) # এক array-কে স্মৃতিতে তোলো
result = set()
for x in nums2:
if x in first: # দুই দিকেই আছে?
result.add(x) # set নিজেই duplicate সামলায়
return list(result)
# ---- tests ---- (set-এর order অনিশ্চিত, তাই sorted দিয়ে মেলাই)
assert sorted(intersection([1, 2, 2, 1], [2, 2])) == [2]
assert sorted(intersection([4, 9, 5], [9, 4, 9, 8, 4])) == [4, 9]
assert sorted(intersection([1, 2, 3], [4, 5, 6])) == []
assert sorted(intersection([], [1, 2])) == []
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `first = set(nums1)` — `nums1`-কে set-এ তুলি; এতে duplicate মুছে যায় আর membership O(1) হয়।
- `result = set()` — common element জমানোর জায়গা; set বলে distinct থাকবে।
- `for x in nums2` — দ্বিতীয় array-র প্রতিটা element নিয়ে দেখি।
- `if x in first` — এটা কি `nums1`-এও ছিল? থাকলে এটা common।
- `result.add(x)` — common হলে যোগ করো; আগে থাকলে set কিছু বদলায় না।
- `return list(result)` — set-কে list বানিয়ে ফেরত (problem list চায়)।
> এক-লাইনের Pythonic বিকল্প: `return list(set(nums1) & set(nums2))` — `&` সরাসরি set intersection ([../operations.md](../operations.md))।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,2,2,1]` ও `[2,2]`: `first={1,2}`, `nums2`-র `2` দুটোই common কিন্তু set-এ একবার → `[2]`। `[4,9,5]` ও `[9,4,9,8,4]`: common `{4,9}` → sorted `[4,9]`। কোনো common না থাকলে `[]`। এক array খালি হলেও `[]`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n + m)** — দুই array একবার করে; set তৈরি ও membership গড়ে O(1) প্রতি element।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n + m)** — `first` set আর `result` set, worst case-এ প্রায় সব element ধরে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- উত্তরে duplicate রেখে দেওয়া — problem distinct চায়; `result`-ও set হওয়া দরকার (বা শেষে dedupe)।
- বড় array-টাকে set-এ তুলে ছোটটায় loop করা — উল্টোটা (ছোটটা set, বড়টায় loop) সাধারণত একটু কম memory খায়; functionally দুটোই ঠিক।
- list-এ membership দিয়ে করা (`x in nums1`) — তখন আবার O(n*m); আসল লাভ set membership থেকেই।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: seen-set (Pattern 4) + set algebra। [../operations.md](../operations.md)-র set-operations অংশ (`&`, `|`, `-`) আর [../patterns.md](../patterns.md)-র Pattern 4 দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Intersection of Two Arrays II —