Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    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] — watch the hash set fill up one value per step, and the final lookup that hits an already-seen number and returns true.

    nums

    01
    12
    23
    31

    scan not started

    seen (hash set)

    empty
    1 / 8
    currentcomparingseenresult

    Start with an empty hash set. Scan left to right and ask one question per number: have I seen this value before?

    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.

    More Arrays & Hashing practice