Contains Duplicate

Problem

Given an integer array nums, return True if any value appears more than once in the array, and False if every element is distinct.

Examples

• nums = [1,2,3,1] → True — the value 1 appears at indices 0 and 3.
• nums = [1,2,3,4] → False — all four values are distinct.
• nums = [1,1,1,3,3,4,3,2,4,2] → True — several values repeat (1, 3, 4, 2).

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9

At 10^5 elements, an O(n^2) pairwise comparison is about 5 * 10^9 operations — you need O(n log n) or better.

Think about it first

TL;DR

Hash set of seen values — O(n) time, O(n) space.

Approach 1 — Brute force

Compare every pair of elements. If any pair matches, there is a duplicate.

from typing import List


def containsDuplicate(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

Complexity: O(n^2) time, O(1) space. With n = 10^5 that is roughly 5 billion comparisons — far past the usual ~10^8 budget, so the constraints kill it.

Approach 2 — Sort first

The insight: sorting forces equal values to become neighbors, so after sorting you only need to compare each element with the one right before it — a single linear scan instead of all pairs.

from typing import List


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

Walkthrough on nums = [1,2,3,1]:

• Sorted: [1,1,2,3].
• i = 1: ordered[1] = 1 equals ordered[0] = 1 → return True immediately.

Complexity: O(n log n) time for the sort, O(n) space for the sorted copy (O(1) extra if you may sort in place). Fast enough, and useful when memory for a hash set is tight.

Approach 3 — Hash set

The insight: you don’t need any ordering at all — you only need to answer “have I seen this exact value before?” in O(1). A hash set does exactly that, so one pass suffices, and you can stop at the first repeat without touching the rest of the array.

from typing import List


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

Walkthrough on nums = [1,2,3,1]:

For nums = [1,2,3,4] the loop finishes with no hit and returns False.

Complexity: O(n) time on average, O(n) space.

A well-known one-liner variant of the same idea builds the whole set up front — return len(set(nums)) < len(nums) — same O(n)/O(n), but it always processes the entire array instead of stopping at the first duplicate.

Common pitfalls

• The O(n^2) double loop is the obvious first idea but exceeds the time budget; state its cost and trade space for time with a hash set.
• Sorting the caller’s list in place (nums.sort()) mutates the input; use sorted(nums) unless mutation is explicitly fine.
• The one-liner len(set(nums)) < len(nums) is elegant but does not short-circuit — on a 10^5-element array whose first two entries match, the early-exit loop wins.
• Don’t overthink value bounds: Python ints hash fine at any size, but in fixed-width languages the ±10^9 range rules out a plain boolean array indexed by value.

Pattern takeaway

This is a core Arrays & Hashing trade: a question about pairs of positions (“do any two indices hold the same value?”) becomes a question about membership (“has this value occurred before?”), which a hash set answers in O(1). Whenever a nested loop exists only to re-find something you already walked past, replace the inner loop with a hash structure keyed on what you’re looking for.