217. Contains Duplicate

217. Contains Duplicate

Difficulty: Easy

Problem Statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

---

Example 1:

Input:
nums = [1, 2, 3, 1]
Output:
true
Explanation:
The element 1 appears more than once (at indices 0 and 3).

---

Example 2:

Input:
nums = [1, 2, 3, 4]
Output:
false
Explanation:
All elements are unique.

---

Example 3:

Input:
nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output:
true
Explanation:
Several elements appear multiple times: 1, 3, 4, and 2.

---

Constraints:

• 1 <= nums.length <= 10⁵

• -10⁹ <= nums[i] <= 10⁹

---

Solution:

 

import java.util.Arrays;

class Solution {

    public boolean containsDuplicate(int[] nums) {

        Arrays.sort(nums); // Sort the array

        for (int i = 1; i < nums.length; i++) {

            if (nums[i] == nums[i - 1]) return true;

        }

        return false;

    }

}

Sure! Let's go through each approach one by one with a simple explanation:

---

✅ 1. Using HashSet (Fast and most common)

HashSet<Integer> seen = new HashSet<>();

for (int num : nums) {

    if (seen.contains(num)) return true;

    seen.add(num);

}

return false;

How it works:

• You keep adding numbers to a HashSet.

• If you try to add a number that's already in the set → it means it's a duplicate → return true.

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

---

✅ 2. Sorting the array

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
if(nums[i] ==nums[i-1])
return true;
        }
        return false;
    }
}
 

How it works:

• First, sort the array.

• Then, check if any two adjacent numbers are equal → if yes, duplicate exists.

Time: O(n log n)
Space: O(1) (if sorting in place)

---

✅ 3. Brute-force (Nested Loops)

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;

How it works:

• Compare each element with every other element.

• If you find any pair that's equal → return true.

Time: O(n²)
Space: O(1)

---

✅ 4. Using HashMap

HashMap<Integer, Boolean> map = new HashMap<>();
for (int num : nums) {
    if (map.containsKey(num)) return true;
    map.put(num, true);
}
return false;

How it works:

• Similar to HashSet, but you're storing each number as a key in a HashMap.

• If the key is already there → it's a duplicate.

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

---

Summary Table:

Approach	Time Complexity	Space Complexity	Fast?	Good for Interviews?
HashSet	O(n)	O(n)	✅	✅✅✅
Sorting	O(n log n)	O(1)	✅	✅✅
Brute-force	O(n²)	O(1)	❌	✅ (for learning only)
HashMap	O(n)	O(n)	✅	✅✅

Which one do you want to try implementing?

Comment below.