Contains Duplicate — Algorithmics

Given a list of numbers, does any value appear more than once?

[]int{2, 7, 3, 7, 9}   // true  — 7 appears twice
[]int{1, 2, 3, 4}      // false — all distinct

The obvious way

Compare every element against every other element:

func containsDuplicate(nums []int) bool {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] == nums[j] {
                return true
            }
        }
    }
    return false
}

Correct, and $O(n^2)$ . For 100,000 numbers that is five billion comparisons — and the worst case is an array with no duplicates at all, because then it never gets to stop early.

The realisation

You do not need to compare pairs. You need to answer one question per element: have I seen this before?

That is not a comparison problem, it is a membership problem — and a hash map answers membership in constant time.

Index 1 / 4

▾ reading 2 0

7 1

3 2

7 3

9 4

seen

2 is new. Add it and move on. The set only ever grows, and each lookup is one hash rather than a scan of everything before it.

Walk left to right, keeping a set of everything seen. If the current value is already in it, stop.

func containsDuplicate(nums []int) bool {
    var seen = make(map[int]bool)

    for _, v := range nums {
        if _, ok := seen[v]; !ok {
            seen[v] = true
        } else {
            return true
        }
    }

    return false
}

$O(n)$ time, $O(n)$ space. One pass.

Two things to tighten

Both are idiom rather than bug; the version above is correct as written.

The comma-ok is doing nothing here. Reading a missing key from a Go map returns the value type’s zero value, and the zero value of bool is false. So seen[v] alone already answers the question:

if _, ok := seen[v]; !ok {
    seen[v] = true
} else {
    return true
}

if seen[v] { return true }
seen[v] = true

The comma-ok form earns its place when you need to distinguish absent from present and zero — a map[string]int where 0 is a legitimate count. Here nothing is ever stored as false, so there is no distinction to draw.

map[T]struct{} is Go's set

Go has no set type, so a map with an ignored value plays the part. struct{} occupies zero bytes, which bool does not:

func containsDuplicate(nums []int) bool {
    seen := make(map[int]struct{}, len(nums))

    for _, v := range nums {
        if _, ok := seen[v]; ok {
            return true
        }
        seen[v] = struct{}{}
    }

    return false
}

The memory saving is small. The reason to prefer it is that the type states the intent — this is a set, not a mapping to a boolean that is always true — and here the comma-ok is required, because struct{}{} carries no information of its own.

Note the len(nums) hint to make. Without it the map rehashes as it grows; with it the buckets are sized once. Free, and it matters at scale.

Sorting instead

func containsDuplicate(nums []int) bool {
    sorted := slices.Clone(nums)
    slices.Sort(sorted)

    for i := 1; i < len(sorted); i++ {
        if sorted[i] == sorted[i-1] {   // duplicates are now adjacent
            return true
        }
    }

    return false
}

$O(n \log n)$ time, and $O(1)$ extra space if you are allowed to sort the caller’s slice in place.

Slower, and the right answer when memory is the binding constraint rather than time — an array too large to hold a set of, or an embedded target. It is the same trade as two pointers versus a hash map, pointing the other way.

What it leads to

The set-as-you-go shape solves a family of problems, and recognising it is worth more than this problem is:

Two Sum — store the value you need, not the value you have.
Contains Duplicate II — same scan, but evict entries more than k indices back, which makes it a sliding window.
Longest consecutive sequence — a set turns “is x + 1 present?” into $O(1)$ and an $O(n \log n)$ sort into $O(n)$ .

In each one the move is identical: replace “search for it” with “ask whether it is there”.