Problem link ও উৎস
- **Original source:** Classic hash set exercise
- **Platform:** LeetCode —
- **Topic:** hash set
- **Difficulty:** Easy
- **Pattern:** seen-set
- **Basic idea inherited from:** complement lookup, যেখানে partner = জিনিসটা নিজেই
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার array `nums` দেওয়া আছে। তোমাকে শুধু বলতে হবে — এতে কি **কোনো একটা সংখ্যা একাধিকবার** আছে? থাকলে `True`, সব আলাদা হলে `False`।
```text
[1, 2, 3, 1] → True (1 দুবার আছে)
[1, 2, 3, 4] → False (সব আলাদা)
```
### Input ও output {#8-example-input-and-output}
```text
Input : [1, 2, 3, 1] Output: True
Input : [1, 2, 3, 4] Output: False
Input : [1, 1, 1, 3, 3, 4, 3, 2, 4, 2] Output: True
Edge : [] Output: False (কিছুই নেই, duplicate নেই)
Edge : [7] Output: False (একটা element)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দরজায় দাঁড়ানো একজন bouncer-এর কথা ভাবো, যে guest list ধরে রাখছে। নতুন কেউ এলে সে দেখে নাম আগে থেকেই তালিকায় আছে কি না — থাকলে বুঝে যায় এই লোক আগেও ঢুকেছে (duplicate)। না থাকলে নাম তুলে ভেতরে ছাড়ে। সেই মাথার তালিকাটাই `set`।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **complement lookup**-এরই একটা সরল ভাই। Two Sum-এ তুমি `target - x` partner খুঁজতে; এখানে partner হলো **জিনিসটা নিজেই** — `x`-এর জন্য খুঁজছ আরেকটা `x`। তাই "আগে দেখেছি কি?" প্রশ্নটাই যথেষ্ট, complement হিসেব করার দরকারও নেই। [../patterns.md](../patterns.md)-এ এটা Pattern 4 — *seen-set*।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: একটা set হলো অতীতের একটা নিখুঁত স্মৃতি। যদি কোনো element ঢোকানোর আগেই সে set-এ থাকে, তার মানে সে আগেও এসেছিল — অর্থাৎ duplicate। মূল invariant: loop-এর প্রতিটা ধাপে `seen`-এ ঠিক ততগুলো **distinct** element থাকে যতগুলো এ পর্যন্ত একবার করে দেখা হয়েছে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash set** (Python-এ `set`)। আমাদের value-র দরকার নেই, শুধু "এই জিনিসটা আগে এসেছে কি না" — existence। তাই `dict` নয়, `set`-ই যথেষ্ট।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Set-এ `x in seen` membership-check গড়ে **O(1)**। List হলে প্রতিবার `x in list` হতো O(n), আর loop-এর ভেতরে সেটা মোট O(n^2)। Set সেই বারবারের খোঁজাকে instant করে দেয় — duplicate ধরার জন্য একদম মাপা hand-glove fit।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা জোড়া (i, j) মিলিয়ে দেখি দুটো সমান কি না।
```text
প্রতিটা i-র জন্য:
প্রতিটা j > i-র জন্য:
nums[i] == nums[j] হলে return True
return False
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop = **O(n^2)**। প্রতিটা element-এর জন্য বাকি পুরো array আবার scan করছি, যদিও "এটা কি আগে এসেছিল" প্রশ্নটার উত্তর একটা set মনে রাখলেই এক ঝলকে পাওয়া যায়। বারবার পুরোটা scan করাই অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: duplicate ধরতে **জোড়া মেলানোর দরকার নেই** — শুধু এ পর্যন্ত দেখা সব element মনে রাখলেই হয়, আর নতুন element সেই স্মৃতিতে আছে কি না দেখলেই হয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা খালি set নিয়ে array-র উপর একবার হাঁটো। প্রতিটা element-এ প্রথমে দেখো সে set-এ আছে কি না — থাকলে duplicate পেয়ে গেছি, `True` ফেরত দাও। না থাকলে তাকে set-এ যোগ করে এগিয়ে যাও। Loop নির্বিঘ্নে শেষ হলে কোনো duplicate ছিল না — `False`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "এটা কি পরে আবার আসবে?" — এই ভবিষ্যৎমুখী প্রশ্নটা উল্টে দাও "এটা কি আগে এসেছিল?"-তে। ভবিষ্যৎ query করা যায় না, কিন্তু অতীত একটা set-এ ধরে রাখা যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1, 2, 3, 1]`। `seen` ধীরে ভরে:
```text
x=1 1 in {}? না → seen={1}
x=2 2 in {1}? না → seen={1, 2}
x=3 3 in {1,2}? না → seen={1, 2, 3}
x=1 1 in {1,2,3}? হ্যাঁ → return True (থেমে গেলাম)
```
খেয়াল করো — duplicate পেলে সঙ্গে সঙ্গে থামি, পুরো array পড়ার দরকার নেই।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums = [1, 2, 3, 1]`:
1. শুরু: `seen = set()` (খালি)।
2. `x=1`: `1 in seen?` না → `seen = {1}`।
3. `x=2`: `2 in seen?` না → `seen = {1, 2}`।
4. `x=3`: `3 in seen?` না → `seen = {1, 2, 3}`।
5. `x=1`: `1 in seen?` হ্যাঁ → return `True`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def contains_duplicate(nums):
seen = set() # অতীতের স্মৃতি
for x in nums:
if x in seen: # আগে দেখেছি?
return True # duplicate!
seen.add(x) # নিজেকে মনে রাখো
return False # কোনো duplicate নেই
# ---- tests ----
assert contains_duplicate([1, 2, 3, 1]) == True
assert contains_duplicate([1, 2, 3, 4]) == False
assert contains_duplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]) == True
assert contains_duplicate([]) == False # খালি array
assert contains_duplicate([7]) == False # একটা element
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `seen = set()` — খালি set, এখানে এ পর্যন্ত দেখা প্রতিটা distinct element জমবে।
- `for x in nums` — array-র প্রতিটা element একবার করে।
- `if x in seen` — এটা কি আগে এসেছিল? `set`-এ এই check গড়ে O(1)।
- `return True` — থাকলে duplicate পাওয়া গেছে, সঙ্গে সঙ্গে থামি।
- `seen.add(x)` — না থাকলে তাকে স্মৃতিতে যোগ করি।
- `return False` — loop নিরাপদে শেষ হলে সব element distinct ছিল।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,2,3,1]`-এ প্রথম তিনটা element নতুন, চতুর্থ `1` আগেই `seen`-এ ছিল → `True`। `[1,2,3,4]`-এ কেউ repeat করে না → `False`। লম্বা mixed array-তে দ্বিতীয় `1`-এই `True`। খালি ও একক-element case-এ loop duplicate পায় না → `False`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
`Set` দিয়ে seen-history — আগে check, পরে add।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// any value seen twice? (seen-set)
function containsDuplicate(nums) {
const seen = new Set(); // অতীতের স্মৃতি
for (const x of nums) {
if (seen.has(x)) return true; // আগে দেখেছি -> duplicate
seen.add(x); // নিজেকে মনে রাখো
}
return false; // সব distinct
}
// ---- test cases (example + edge) ----
assert(containsDuplicate([1, 2, 3, 1]) === true, "has-dup");
assert(containsDuplicate([1, 2, 3, 4]) === false, "all-distinct");
assert(containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]) === true, "many");
assert(containsDuplicate([]) === false, "empty"); // edge
assert(containsDuplicate([7]) === false, "single"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** `Set.has` average O(1) (array `includes` O(n) হতো)। boolean-এর জন্য JS-এ `true`/`false` literal; check অবশ্যই `add`-এর আগে, নইলে প্রতিটা element নিজেকেই duplicate ভাববে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function containsDuplicate(nums: number[]): boolean {
const seen: Set