217. Contains Duplicate
Tags: leetcode, dsa, coding, programming
Published: 2024-04-22 22:47:31

## 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:

```
Input: nums = [1,2,3,1]
Output: true

Input: nums = [1,2,3,4]
Output: false

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
```
## Approach 1: Brute Force

This approach is straightforward but has a time complexity of O(n^2), making it less efficient for large arrays.

```
class Solution {
    public boolean containsDuplicate(int[] nums) {
        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;
    }
}
```
Got TLE for this code

**Constraints:**
    `1 <= nums.length <= 105`
    `-109 <= nums[i] <= 109`

## Approach 2: Sorting

Sorting helps in bringing duplicates together, simplifying the check. However, sorting has a time complexity of O(n log n).

```
class Solution {
    public boolean containsDuplicate(int[] nums) {

        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }

        return false;
    }
}
```

Runtime: 20ms

## Approach 3: HashSet

```
// Time complexity: O(n)
// Space complexity: O(n)
class Solution {
    public boolean containsDuplicate(int[] nums) {

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

        for(int i=0;i<nums.length;i++){
            if(hashset.contains(nums[i])){
                return true;
            }
            hashset.add(nums[i]);
        }
        return false;
    }
}
```
Runtime: 12ms

## Approach 4: HashMap

```
class Solution {
    public boolean containsDuplicate(int[] nums) {

        Map<Integer, Boolean> mp = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (mp.containsKey(nums[i])) {
                return true;
            }
            mp.put(nums[i], true);
        }
        return false;
    }
}
```
Runtime: 12ms

## Approach 5: Set

```
class Solution {
    public boolean containsDuplicate(int[] nums) {

        Set<Integer> set = new HashSet<>();

        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            }
            set.add(num);
        }

        return false;
    }
}
```
Runtime: 10ms

**Learnings:**
- Time Complexity
- Sorting
- HashSet
- HashMap
- Set

Solution with Comments:

```
import java.util.HashSet;
import java.util.Set;

public class ContainsDuplicate {

    public static boolean containsDuplicate(int[] nums) {
        // Step 1: Create a HashSet to store unique elements
        Set<Integer> seen = new HashSet<>();
        
        // Step 2: Iterate through the array
        for (int num : nums) {
            // Step 3: Check if the element is already in the set (duplicate)
            if (seen.contains(num)) {
                // Step 4: If duplicate found, return true
                return true;
            }
            // Step 5: Add the element to the set
            seen.add(num);
        }
        
        // Step 6: If loop completes, no duplicates found, return false
        return false;
    }

    public static void main(String[] args) {
        // Test cases
        int[] nums1 = {1, 2, 3, 1};
        System.out.println(containsDuplicate(nums1));  // Output: true
        
        int[] nums2 = {1, 2, 3, 4};
        System.out.println(containsDuplicate(nums2));  // Output: false
        
        int[] nums3 = {1, 1, 1, 3, 3, 4, 3, 2, 4, 2};
        System.out.println(containsDuplicate(nums3));  // Output: true
    }
}
```

**Time Complexity Analysis:**

- HashSet Operations: The key operations affecting time complexity in this solution are contains(num) and add(num) on the HashSet.

- Contains Operation: Checking if an element is in a HashSet (using contains) has an average time complexity of O(1). This is because HashSet uses hashing to store elements, allowing for constant-time lookups on average.

- Add Operation: Adding an element to a HashSet (using add) also has an average time complexity of O(1), assuming the hash function distributes elements uniformly.

- Loop Iteration: The for loop in the containsDuplicate function iterates through each element in the input array once.

**Overall Time Complexity:**

- O(n): Considering all the operations together, the time complexity of the containsDuplicate function is O(n), where n is the number of elements in the input array nums.

- Each num in the array is either added to the HashSet (O(1)) or checked if it's already in the HashSet (O(1)).

- Since we have a single loop that goes through each element once, the time complexity is linear with respect to the input size.

**Step-by-Step Explanation:**

**1. Create a Set:** We create a HashSet named seen to store unique elements from the input array nums. HashSet allows for constant time (O(1)) lookup.

**2. Iterate through the Array:** We iterate through the given array nums using an enhanced for-loop (`for (int num : nums)`).

**3. Check for Duplicate:** For each element num in the array, we check if it is already in the seen set. We use `seen.contains(num)` to check if the element is a duplicate.

**4. Return True if Duplicate Found:** If seen already contains num, it means we've found a duplicate. We return true immediately.

**5. Add to Set:** If num is not in the seen set, it is a new element, so we add it to the seen set using `seen.add(num)`.

**6. Return False if No Duplicates:** If the loop completes without finding any duplicates, we return false because there are no duplicates in the array.

5 Problems similar to **_217 Contains Duplicate_** leetcode problem

1. [219. Contains Duplicate II](https://leetcode.com/problems/contains-duplicate-ii/description/)
2. [220. Contains Duplicate III](https://leetcode.com/problems/contains-duplicate-iii/description/)
3. [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/description/)
4. [645. Set Mismatch](https://leetcode.com/problems/set-mismatch/description/)
5. [448. Find All Numbers Disappeared in an Array](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/)