Contains Duplicate

Easyarrayhash-tablesorting
Category: Array & Hashing
Companies that ask this question:
AmazonAppleMicrosoftGoogle
LeetCode →NeetCode →

Approach

Contains Duplicate

Problem

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

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

Example 2:

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

Example 3:

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

Approach 1: HashSet (Optimal - O(n))

Intuition

Use a HashSet to track numbers we've seen. If we encounter a number that's already in the set, we've found a duplicate.

Algorithm

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Time Complexity

  • O(n): Single pass through the array
  • HashSet operations (add, lookup) are O(1) average case

Space Complexity

  • O(n): HashSet can store up to n unique elements

Approach 2: Sorting - O(n log n)

Intuition

Sort the array first. Duplicates will be adjacent after sorting.

Algorithm

def containsDuplicate(nums):
    nums.sort()
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False

Time Complexity

  • O(n log n): Sorting dominates

Space Complexity

  • O(1): If sorting in-place (depends on sort implementation)
  • O(n): If using additional space for sorting

Approach 3: Set Length Comparison - O(n)

Intuition

If the set has fewer elements than the array, there must be duplicates.

Algorithm

def containsDuplicate(nums):
    return len(set(nums)) < len(nums)

Time Complexity

  • O(n): Creating set requires iterating through all elements

Space Complexity

  • O(n): Set storage

Which Approach to Use?

  • HashSet (Approach 1): Best for early termination when duplicate found quickly
  • Sorting (Approach 2): Good if you need sorted array anyway, or limited memory
  • Set Length (Approach 3): Most concise, but always processes entire array

Solution

java
1/**
2 * Contains Duplicate
3 * Time: O(n) with HashSet, O(n log n) with sorting
4 * Space: O(n) with HashSet, O(1) or O(n) with sorting
5 */
6
7import java.util.*;
8
9// Approach 1: HashSet (Optimal - O(n))
10class Solution {
11    public boolean containsDuplicate(int[] nums) {
12        Set<Integer> seen = new HashSet<>();
13        for (int num : nums) {
14            if (seen.contains(num)) {
15                return true;
16            }
17            seen.add(num);
18        }
19        return false;
20    }
21}
22
23// Approach 2: Sorting - O(n log n)
24class Solution2 {
25    public boolean containsDuplicate(int[] nums) {
26        Arrays.sort(nums);
27        for (int i = 0; i < nums.length - 1; i++) {
28            if (nums[i] == nums[i + 1]) {
29                return true;
30            }
31        }
32        return false;
33    }
34}
35
36// Approach 3: Set Size Comparison - O(n)
37class Solution3 {
38    public boolean containsDuplicate(int[] nums) {
39        Set<Integer> set = new HashSet<>();
40        for (int num : nums) {
41            set.add(num);
42        }
43        return set.size() < nums.length;
44    }
45}
46
47// Approach 4: HashMap with frequency counting
48class Solution4 {
49    public boolean containsDuplicate(int[] nums) {
50        Map<Integer, Integer> freq = new HashMap<>();
51        for (int num : nums) {
52            if (freq.containsKey(num)) {
53                return true;
54            }
55            freq.put(num, 1);
56        }
57        return false;
58    }
59}
60
Loading visualizer...