LC #217: Contains Duplicate

🧠 Problem Statement

Check if any element appears more than once in the array.

🔗 Leetcode Link

Contains Duplicate - LC #217

---

💥 Brute Force

for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[i] == nums[j]) return true;
    }
}
return false;

• Time: O(n²) ← nested loop
• Space: O(1)

✅ Works, but super slow for big inputs.

---

⚡ Optimized: HashSet FTW

Set<Integer> seen = new HashSet<>();
for (int num : nums) {
    if (seen.contains(num)) return true;
    seen.add(num);
}
return false;

• Time: O(n)
• Space: O(n)

💡 Why better? Because .contains() and .add() in HashSet = O(1) time.

---

🧪 Test Case 1: Duplicate Present

Input: [1, 2, 3, 1] Expected Output: true

🔍 Dry Run:

• seen = {}
• 1 → not seen → add → {1}
• 2 → not seen → add → {1,2}
• 3 → not seen → add → {1,2,3}
• 1 → already seen → return true

---

🧪 Test Case 2: All Unique

Input: [10, 20, 30, 40] Expected Output: false

🔍 Dry Run:

• seen = {}
• 10 → not seen → add → {10}
• 20 → not seen → add → {10,20}
• 30 → not seen → add → {10,20,30}
• 40 → not seen → add → {10,20,30,40}
• Done → return false

---

🔁 Similar Problems

• LeetCode #219 – Contains Duplicate II (within k indices)
• LeetCode #3 – Longest Substring Without Repeating Characters (sliding window)