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

Comments

[Andy Nian]

Sorting the array to check for duplicates works, but using a HashSet gives you a cleaner O(n) solution. Sorting can be overkill, especially with larger datasets. I usually use LeetCode for DSA practice, but I've been using PracHub for technical rounds, and their question banks are much better than random blog posts.