Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Contains Duplicate

Contains Duplicate

Master this topic with zero to advance depth.

Contains Duplicate

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.

Visual Representation

nums = [1, 2, 3, 1] Using HashSet: - 1: Not in set. Set={1} - 2: Not in set. Set={1, 2} - 3: Not in set. Set={1, 2, 3} - 1: EXISTS in set! -> Return True
Easy

Examples

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

Level I: Brute Force

Intuition

Compare every pair of elements. If any pair is identical, return true.

⏱ O(N²)💾 O(1)

Detailed Dry Run

[1, 2, 1] (1, 2): No (1, 1): MATCH! True

java
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;
    }
}
Approach 2

Level II: Sorting

Intuition

If duplicates exist, they will be adjacent when sorted.

⏱ O(N log N)💾 O(1) if sorting in-place.

Detailed Dry Run

[1, 2, 3, 1] -> Sort -> [1, 1, 2, 3] nums[0] == nums[1] (1 == 1) -> True

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

Level III: HashSet (Optimal)

Intuition

Checking membership in a HashSet takes O(1) average time. If an element is already in the set, a duplicate is found.

⏱ O(N)💾 O(N)

Detailed Dry Run

[1, 2, 3, 1] Map {} -> {1} -> {1, 2} -> {1, 2, 3} -> Contains 1! True

java
import java.util.*;
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (set.contains(n)) return true;
            set.add(n);
        }
        return false;
    }
}
← Previous QuestionValid Anagram
Next Question →Group Anagrams