Contains Duplicate

easy
Arrays & HashingArrayHash TableSorting

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.

Examples

Example 1

  • Input: nums = [1,2,3,1]
  • Output: true
  • Explanation: The element 1 occurs at indices 0 and 3.

Example 2

  • Input: nums = [1,2,3,4]
  • Output: false
  • Explanation: All elements are distinct.

Example 3

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

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Sorting

Intuition

If we sort the array, any duplicate elements will become adjacent to each other. We can then make a single pass through the sorted array and check if any two consecutive elements are equal. This avoids the need for extra data structures but modifies the input array and has O(n log n) time due to sorting. It is a good approach when space is a concern.

Algorithm

  1. Sort the array in non-decreasing order.
  2. Iterate through the sorted array from index 1 to n-1.
  3. At each index i, compare nums[i] with nums[i-1].
  4. If they are equal, a duplicate exists -- return true.
  5. If the loop completes without finding any adjacent duplicates, return false.
TimeO(n log n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }

        return false;
    }
};
Java 21
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;
    }
}
Python 3.12
def containsDuplicate(nums: list[int]) -> bool:
    nums.sort()

    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True

    return False
Go 1.26
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
}
Approach 2

Hash Set

Intuition

A hash set provides O(1) average-time lookups and insertions, making it ideal for duplicate detection. As we iterate through the array, we check if the current element already exists in the set. If it does, we have found a duplicate and can return immediately. If not, we add it to the set and continue. This is the optimal approach for this problem, trading O(n) space for O(n) time. In practice, it is often faster than sorting because it can short-circuit as soon as a duplicate is found.

Algorithm

  1. Create an empty hash set.
  2. Iterate through each element in the array.
  3. For each element, check if it already exists in the set.
  4. If it exists, return true -- a duplicate has been found.
  5. If it does not exist, add it to the set and continue.
  6. If the loop finishes without finding a duplicate, return false.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
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 21
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;
    }
}
Python 3.12
def containsDuplicate(nums: list[int]) -> bool:
    seen = set()

    for num in nums:
        if num in seen:
            return True
        seen.add(num)

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

Frequently asked questions

What is the optimal time complexity of Contains Duplicate?

The most efficient approach in this guide ("Hash Set") runs in O(n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Contains Duplicate use?

Contains Duplicate is a easy-level Arrays & Hashing problem involving Array, Hash Table, Sorting. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Contains Duplicate be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Two Sum

Original problem: leetcode.com

Loading editor...
Input
nums=
[1,2,3,1]
Expected Output
true