Interview Sheet Q3:- 217. Contains Duplicate

1. Brute Force Approach

Compare every element with every other element.
If any pair is equal → duplicate exists.

Time Complexity: O(n²)

Code

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;
    }
}

2. Sorting Approach

Sort the array.
Duplicate elements will become adjacent.
Compare neighboring elements.

Time Complexity: O(n log n)

Code

import java.util.Arrays;

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;
    }
}

3. HashSet Approach (Optimal)

Why Optimal?

We only need fast checking of already seen elements.
HashSet gives near O(1) lookup and insertion.
Array is traversed only once.

Time Complexity: O(n)

Code

import java.util.HashSet;

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

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

        for (int num : nums) {

            if (set.contains(num)) {
                return true;
            }

            set.add(num);
        }

        return false;
    }
}