Course4all

Contains Duplicate

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Arrays & Hashing.

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

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionValid Anagram
Next Question →Group Anagrams