DSAPrep
EasyArrays & 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.

Example 1

Input: nums = [1,2,3,1]
Output: true
Explanation: The element 1 occurs at the 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
View original on LeetCode ↗

The question is really just “have I seen this number before?” repeated for every element. Answering that question fast — in O(1) instead of by rescanning — is what separates the brute force from the optimal solution.

Brute Force

Time O(n²)Space O(1)

Compare every pair of elements. If any two match, return true.

class Solution:
    def hasDuplicate(self, nums: list[int]) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j]:
                    return True
        return False

Correct, since it checks every possible pair, but for each of the n starting indices it may rescan almost the entire rest of the array — O(n²) comparisons in the worst case (no duplicates at all).

Sort First

Time O(n log n)Space O(1)

If we sort the array, duplicates end up next to each other. A single linear pass then checks adjacent pairs.

class Solution:
    def hasDuplicate(self, nums: list[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

Sorting dominates the cost at O(n log n), and an in-place sort needs no extra array — O(1) auxiliary space (ignoring the sort’s own recursion stack). Better than brute force, but we can still do better by trading a little space for linear time.

Hash Set

OptimalTime O(n)Space O(n)

Walk the array once, keeping a set of numbers seen so far. Before adding the current number, check whether it is already in the set — if it is, we have found our duplicate immediately.

class Solution:
    def hasDuplicate(self, nums: list[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

Tracing nums = [1, 2, 3, 1]:

1
0
2
1
3
2
1
3
num = 1

Hash Map

1 → seen
1 / 4
resultcurrent

num=1 is not in the set yet. Add it.

Correctness: the set always holds exactly the elements seen before the current index, so a hit means some earlier index shares this value — a true duplicate. If the loop finishes without a hit, every element was distinct.

Complexity: each of the n elements does one average-case O(1) set lookup and insert — O(n) time. The set can grow to hold all n elements — O(n) space. This trades the sort’s O(n log n) for linear time by spending memory instead.