002 — Contains Duplicate

Problem link ও উৎস

• 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 = জিনিসটা নিজেই

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

উদাহরণ

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

Input ও 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)

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা complement lookup-এরই একটা সরল ভাই। Two Sum-এ তুমি target - x partner খুঁজতে; এখানে partner হলো জিনিসটা নিজেই — x-এর জন্য খুঁজছ আরেকটা x। তাই "আগে দেখেছি কি?" প্রশ্নটাই যথেষ্ট, complement হিসেব করার দরকারও নেই। ../patterns.md-এ এটা Pattern 4 — seen-set।

ভেতরের যুক্তি

লুকানো logic: একটা set হলো অতীতের একটা নিখুঁত স্মৃতি। যদি কোনো element ঢোকানোর আগেই সে set-এ থাকে, তার মানে সে আগেও এসেছিল — অর্থাৎ duplicate। মূল invariant: loop-এর প্রতিটা ধাপে seen-এ ঠিক ততগুলো distinct element থাকে যতগুলো এ পর্যন্ত একবার করে দেখা হয়েছে।

কী দিয়ে তথ্য রাখব

একটা hash set (Python-এ set)। আমাদের value-র দরকার নেই, শুধু "এই জিনিসটা আগে এসেছে কি না" — existence। তাই dict নয়, set-ই যথেষ্ট।

এটি কেন উপযুক্ত

Set-এ x in seen membership-check গড়ে O(1)। List হলে প্রতিবার x in list হতো O(n), আর loop-এর ভেতরে সেটা মোট O(n^2)। Set সেই বারবারের খোঁজাকে instant করে দেয় — duplicate ধরার জন্য একদম মাপা hand-glove fit।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ

প্রতিটা i-র জন্য:
    প্রতিটা j > i-র জন্য:
        nums[i] == nums[j] হলে return True
return False

কোথায় বেশি কাজ হচ্ছে

দুটো nested loop = O(n^2)। প্রতিটা element-এর জন্য বাকি পুরো array আবার scan করছি, যদিও "এটা কি আগে এসেছিল" প্রশ্নটার উত্তর একটা set মনে রাখলেই এক ঝলকে পাওয়া যায়। বারবার পুরোটা scan করাই অপচয়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: duplicate ধরতে জোড়া মেলানোর দরকার নেই — শুধু এ পর্যন্ত দেখা সব element মনে রাখলেই হয়, আর নতুন element সেই স্মৃতিতে আছে কি না দেখলেই হয়।

আরও কম কাজে সমাধান

একটা খালি set নিয়ে array-র উপর একবার হাঁটো। প্রতিটা element-এ প্রথমে দেখো সে set-এ আছে কি না — থাকলে duplicate পেয়ে গেছি, True ফেরত দাও। না থাকলে তাকে set-এ যোগ করে এগিয়ে যাও। Loop নির্বিঘ্নে শেষ হলে কোনো duplicate ছিল না — False।

ভাবনার পরিবর্তন

মোচড়: "এটা কি পরে আবার আসবে?" — এই ভবিষ্যৎমুখী প্রশ্নটা উল্টে দাও "এটা কি আগে এসেছিল?"-তে। ভবিষ্যৎ query করা যায় না, কিন্তু অতীত একটা set-এ ধরে রাখা যায়।

ছবিতে বোঝা

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

ছোট input-এ ধাপে ধাপে

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।

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

[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

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

TypeScript

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-ও পাকা।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

• 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)

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

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

কোথায় কাজে লাগে

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