Contains Duplicate

Problem Statement

Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.

What to notice first

• You only need to find one duplicate — you can stop as soon as you find it.
• The fastest approach avoids sorting by using a hash set to check membership in O(1).
• The sorting approach trades speed for zero extra memory beyond the sort itself.

Examples

Input	Output	Explanation
[1, 2, 3, 1]	true	1 appears at indices 0 and 3
[1, 2, 3, 4]	false	All elements are distinct
[1, 1, 1, 3, 3, 4, 3, 2, 4, 2]	true	Multiple duplicates present

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Real-World Applications

Where this pattern appears

• User ID deduplication — check whether a batch of new user IDs contains any that are already registered.
• Transaction fraud detection — flag whether the same transaction ID appears more than once in a batch.
• File integrity — verify that a list of file checksums has no repeated entries (which would indicate collisions).
• Inventory management — confirm that a list of product SKUs contains no accidental duplicates before importing.

Complexity Comparison

Approach	Time	Space	Best When
Hash Set	O(n)	O(n)	General case — fast lookup, stop early on first duplicate
Sorting	O(n log n)	O(1)	Memory is constrained and you can afford extra time

Which approach should you learn first?

• Pick Hash Set for interviews — O(n) with early exit is the expected answer.
• Pick Sorting if you need to understand the space trade-off or the interviewer bans extra memory.

Best For Speed

Hash Set

O(n) time · O(n) space

No Extra Memory

Sorting

O(n log n) time · O(1) space

Approach 1: Hash Set

★ Recommended

Scan the array once. For each number, check if it is already in the set. If yes, return true immediately. Otherwise add it to the set and continue. A hash set gives O(1) average lookup and insert.

⏱ Time O(n) Single pass, early exit 💾 Space O(n) Set stores up to n elements

Step-by-step Example

Input: [1, 2, 3, 1]

Step	num	In seen?	seen after
1	1	No	{1}
2	2	No	{1, 2}
3	3	No	{1, 2, 3}
4	1	Yes → return true	—

Animated walkthrough

How the hash set scan detects a duplicate

Use Next or Autoplay to see each number checked against the set and either stored or flagged as a duplicate.

Back Autoplay Next Reset

Step 1 of 5

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function containsDuplicate(nums):
    seen = {}
    for num in nums:
        if num in seen:
            return true
        seen.add(num)
    return false

Solution Code

Python

contains_duplicate_hash_set.py

from typing import List


def contains_duplicate(nums: List[int]) -> bool:
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

C++

contains_duplicate_hash_set.cpp

#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> seen;
        for (int num : nums) {
            if (seen.count(num)) return true;
            seen.insert(num);
        }
        return false;
    }
};

Java

contains_duplicate_hash_set.java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) return true;
            seen.add(num);
        }
        return false;
    }
}

JavaScript

contains_duplicate_hash_set.js

function containsDuplicate(nums) {
    const seen = new Set();
    for (const num of nums) {
        if (seen.has(num)) return true;
        seen.add(num);
    }
    return false;
}

Rust

contains_duplicate_hash_set.rs

use std::collections::HashSet;

impl Solution {
    pub fn contains_duplicate(nums: Vec<i32>) -> bool {
        let mut seen = HashSet::new();
        for num in nums {
            if !seen.insert(num) {
                return true;
            }
        }
        false
    }
}

Go

contains_duplicate_hash_set.go

func containsDuplicate(nums []int) bool {
    seen := map[int]bool{}
    for _, num := range nums {
        if seen[num] {
            return true
        }
        seen[num] = true
    }
    return false
}

Approach 2: Sorting

✓ Simple

Sort the array first. After sorting, any duplicate values must be adjacent. A single pass then detects any pair of equal neighbours.

⏱ Time O(n log n) Dominated by sort 💾 Space O(1) In-place sort, no extra structure

Step-by-step Example

Input: [3, 1, 3, 2]

After sorting: [1, 3, 3, 2] → wait: [1, 2, 3, 3]

i	nums[i]	nums[i-1]	Equal?
1	2	1	No
2	3	2	No
3	3	3	Yes → return true

Pseudocode

function containsDuplicate(nums):
    sort(nums)
    for i from 1 to len(nums) - 1:
        if nums[i] == nums[i - 1]:
            return true
    return false

Solution Code

Python

contains_duplicate_sorting.py

from typing import List


def contains_duplicate(nums: List[int]) -> bool:
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False


print(contains_duplicate([1, 2, 3, 1]))  # True
print(contains_duplicate([1, 2, 3, 4]))  # False

C++

contains_duplicate_sorting.cpp

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 1; i < (int)nums.size(); i++) {
            if (nums[i] == nums[i - 1]) return true;
        }
        return false;
    }
};

Java

contains_duplicate_sorting.java

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

JavaScript

contains_duplicate_sorting.js

function containsDuplicate(nums) {
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) return true;
    }
    return false;
}

Rust

contains_duplicate_sorting.rs

impl Solution {
    pub fn contains_duplicate(mut nums: Vec<i32>) -> bool {
        nums.sort_unstable();
        nums.windows(2).any(|w| w[0] == w[1])
    }
}

Go

contains_duplicate_sorting.go

package golang
import "sort"

func containsDuplicate(nums []int) bool {
  sort.Ints(nums)
  for i := 1; i < len(nums); i++ {
    if nums[i] == nums[i-1] {
      return true
    }
  }


}  return false

Watch for these pitfalls

• Using == on the wrong indices — compare nums[i] with nums[i-1], not nums[i+1], to avoid an off-by-one out-of-bounds.
• Forgetting that sorting mutates the input — if the caller needs the original order, sort a copy.
• In the hash set approach, do not insert before checking — insert after, so you don’t accidentally match a number against itself.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

contains_duplicate_space_optimized.py

"""
Solution for Contains Duplicate
"""

def solve():
    """Implementation for approach 3 of Contains Duplicate"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

contains_duplicate_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Contains Duplicate
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ContainsDuplicateSpaceOptimized.java

/**
 * Solution for Contains Duplicate
 * Approach 3
 */
public class ContainsDuplicateSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

contains_duplicate_space_optimized.js

/**
 * Solution for Contains Duplicate
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

contains_duplicate_space_optimized.rs

/// Solution for Contains Duplicate
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

contains_duplicate_space_optimized.go

package main

import "fmt"

// Solution for Contains Duplicate
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Two Sum Easy #1
• Valid Anagram Easy #242
• Intersection of Two Arrays Easy #349
• Contains Duplicate II ↗ Medium #219

Interview Tips

Key trade-offs to discuss

• Why hash set over sorting? O(n) vs O(n log n), and the hash set exits as soon as the first duplicate is found — often much earlier in practice.
• Follow-up — no extra space? The sorting approach is the answer. Be ready to discuss that it mutates the input and takes O(n log n) time.
• Edge cases to mention: single-element array (always false), all identical elements (immediately true after the first element is added), negative numbers (handled transparently by a hash set).

← Previous
#215 Kth Largest Element in Array Next
#219 Contains Duplicate II →