002 — Contains Duplicate¶

Source¶

Original source: Classic hash set exercise
Platform: LeetCode — https://leetcode.com/problems/contains-duplicate/
Topic: hash set
Difficulty: Easy
Pattern: seen-set
Basic idea inherited from: complement lookup, যেখানে partner = জিনিসটা নিজেই

1. Problem in simple words¶

একটা সংখ্যার array nums দেওয়া আছে। তোমাকে শুধু বলতে হবে — এতে কি কোনো একটা সংখ্যা একাধিকবার আছে? থাকলে True, সব আলাদা হলে False।

[1, 2, 3, 1]  →  True   (1 দুবার আছে)
[1, 2, 3, 4]  →  False  (সব আলাদা)

2. Which basic idea does this inherit from?¶

এটা complement lookup-এরই একটা সরল ভাই। Two Sum-এ তুমি target - x partner খুঁজতে; এখানে partner হলো জিনিসটা নিজেই — x-এর জন্য খুঁজছ আরেকটা x। তাই "আগে দেখেছি কি?" প্রশ্নটাই যথেষ্ট, complement হিসেব করার দরকারও নেই। ../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।

6. Real-life analogy¶

দরজায় দাঁড়ানো একজন bouncer-এর কথা ভাবো, যে guest list ধরে রাখছে। নতুন কেউ এলে সে দেখে নাম আগে থেকেই তালিকায় আছে কি না — থাকলে বুঝে যায় এই লোক আগেও ঢুকেছে (duplicate)। না থাকলে নাম তুলে ভেতরে ছাড়ে। সেই মাথার তালিকাটাই set।

7. Visual explanation¶

nums = [1, 2, 3, 1]। seen ধীরে ভরে:

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 পড়ার দরকার নেই।

8. Example input and output¶

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)

9. Brute force thinking¶

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

প্রতিটা 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-এ ধরে রাখা যায়।

14. Step-by-step dry run¶

Input nums = [1, 2, 3, 1]:

শুরু: seen = set() (খালি)।
x=1: 1 in seen? না → seen = {1}।
x=2: 2 in seen? না → seen = {1, 2}।
x=3: 3 in seen? না → seen = {1, 2, 3}।
x=1: 1 in seen? হ্যাঁ → return True।

15. Python solution¶

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 ছিল।

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

18. Time complexity¶

O(n) — প্রতিটা element একবার করে দেখি, প্রতিবার set operation গড়ে O(1)।

19. Space complexity¶

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

20. Common mistakes¶

seen.add(x) check-এর আগে করে ফেলা — তখন প্রতিটা element নিজেকেই "আগে দেখা" মনে করে সবসময় True দেয়। আগে check, পরে add।
existence-এর জন্য set-এর বদলে dict বা list নেওয়া — list-এ membership O(n), পুরো লাভটাই মাটি।
খালি array আলাদা করে না ভাবা — যদিও এই code-এ loop চলেই না, তাই এমনিতেই False ঠিক আসে।

21. Which basic problem this inherits from¶

ভিত্তি: Two Sum-এর complement lookup, এক ধাপ সরল করে (partner = জিনিসটা নিজেই)। ../concept.md-র has_duplicate snippet আর ../patterns.md-র Pattern 4 দেখো।

22. Similar harder problems¶

Contains Duplicate II — https://leetcode.com/problems/contains-duplicate-ii/ (duplicate-দের index দূরত্ব k-র মধ্যে কি না)
Longest Consecutive Sequence — https://leetcode.com/problems/longest-consecutive-sequence/ (এই tracker-এর #12; set-এ পুরো array, তারপর smart run-গোনা)
Intersection of Two Arrays — https://leetcode.com/problems/intersection-of-two-arrays/ (#6; এক array-কে set বানিয়ে অন্যটায় membership)

23. Pattern learned¶

Seen-set: "আগে দেখেছি?" প্রশ্নের O(1) উত্তরের জন্য একটা set-এ অতীত জমিয়ে রাখো — duplicate, visited, distinct — সবের ভিত।

24. Final summary¶

ভবিষ্যতের আমাকে: "duplicate / আগে এসেছে কি / distinct" শুনলেই set। অতীত মনে রাখো, নতুন জিনিস সেই স্মৃতিতে আছে কি না দেখো। এই একই seen-set পরে graph-এর visited set হয়ে ফিরে আসবে।

25. JavaScript solution (with test cases)¶

Set দিয়ে seen-history — আগে check, পরে add।

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 ভাববে।

26. TypeScript solution (with test cases)¶

function containsDuplicate(nums: number[]): boolean {
  const seen: Set<number> = new Set();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(containsDuplicate([1, 2, 3, 1]), true, "has-dup");
expect(containsDuplicate([1, 2, 3, 4]), false, "all-distinct");
expect(containsDuplicate([]), false, "empty");
console.log("সব TS test pass!");

TS টীকা: return type boolean declare করায় ভুল করে number/undefined ফেরত দিলে compiler ধরে; Set<number> element type-ও পাকা।

27. কোথায় কাজে লাগে (real-world use)¶

Duplicate submission guard: form/API request-এ একই id দুবার এলে reject করা (idempotency key check)।
Fraud/abuse detection: একই device/IP একাধিকবার দেখা গেলে flag করা।
Data dedup pipeline: ingest করার আগে duplicate record দ্রুত চিহ্নিত করা।
Graph traversal: visited set দিয়ে একই node দুবার process আটকানো (এই seen-set-ই সেখানে ফিরে আসে)।
Inventory/SKU: duplicate barcode/serial আছে কিনা যাচাই।
Voting/poll integrity: একই voter দুবার ভোট দিয়েছে কিনা ধরা।

মূল pattern: অতীত মনে রাখো, নতুন জিনিস সেই স্মৃতিতে আছে কিনা দেখো — "duplicate / আগে এসেছে / distinct" দেখলেই seen-set।

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