217. Contains Duplicate (Easy)

Problem

Given an integer array nums, return true if any value appears at least twice in the array, and false if every element is distinct.

Examples

nums = [1, 2, 3, 1] → true
nums = [1, 2, 3, 4] → false
nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2] → true

LeetCode 217 · Link · Easy

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, check every pair

Compare every element with every element after it. If any two match, return true.

def contains_duplicate(nums: list[int]) -> bool:
    n = len(nums)                              # L1: O(1)
    for i in range(n):                         # L2: outer loop, n iterations
        for j in range(i + 1, n):             # L3: inner loop, up to n-i-1 iterations
            if nums[i] == nums[j]:             # L4: O(1) comparison
                return True                    # L5: O(1) early return
    return False

function containsDuplicate(nums: number[]): boolean {
    const n = nums.length;                          // L1: O(1)
    for (let i = 0; i < n; i++) {                  // L2: outer loop, n iterations
        for (let j = i + 1; j < n; j++) {          // L3: inner loop, up to n-i-1 iterations
            if (nums[i] === nums[j]) return true;   // L4-L5: O(1) comparison + early return
        }
    }
    return false;
}

func containsDuplicate(nums []int) bool {
  n := len(nums)                             // L1: O(1)
  for i := 0; i < n; i++ {                  // L2: outer loop, n iterations
    for j := i + 1; j < n; j++ {          // L3: inner loop, up to n-i-1 iterations
      if nums[i] == nums[j] {            // L4: O(1) comparison
        return true                    // L5: O(1) early return
      }
    }
  }
  return false
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (len)	$O(1)$	1	$O(1)$
L2 (outer loop)	$O(1)$	n	$O(n)$
L3, L4 (inner loop + compare)	$O(1)$	~n²/2 worst case	$O(n²)$ ← dominates
L5 (return)	$O(1)$	at most 1	$O(1)$

The nested loops each run up to n, yielding ~n²/2 comparisons in the worst case (no duplicates).

Complexity

Time: $O(n²)$ , driven by L3/L4 (nested loop comparisons).
Space: $O(1)$ . No extra structures; only the loop indices.

This is the most direct approach but quadratic time makes it unusable for large inputs.

Swift

final class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        for i in nums.indices { for j in (i + 1)..<nums.count where nums[i] == nums[j] { return true } }
        return false
    }
}

Approach 2: Sort and compare adjacent

After sorting, any duplicates are adjacent. One linear scan is enough.

def contains_duplicate(nums: list[int]) -> bool:
    nums_sorted = sorted(nums)                    # L1: O(n log n), new list
    for i in range(1, len(nums_sorted)):          # L2: loop, n-1 iterations
        if nums_sorted[i] == nums_sorted[i - 1]:  # L3: O(1) comparison
            return True                           # L4: O(1) early return
    return False

function containsDuplicate(nums: number[]): boolean {
    const sorted = [...nums].sort((a, b) => a - b); // L1: O(n log n)
    for (let i = 1; i < sorted.length; i++) {        // L2: loop, n-1 iterations
        if (sorted[i] === sorted[i - 1]) return true; // L3-L4: O(1) comparison + return
    }
    return false;
}

func containsDuplicate(nums []int) bool {
  sorted := make([]int, len(nums))
  copy(sorted, nums)
  sort.Ints(sorted)                                  // L1: O(n log n)
  for i := 1; i < len(sorted); i++ {                // L2: loop, n-1 iterations
    if sorted[i] == sorted[i-1] { return true }   // L3-L4: O(1) comparison + return
  }
  return false
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L2, L3 (linear scan)	$O(1)$	n-1	$O(n)$
L4 (return)	$O(1)$	at most 1	$O(1)$

The sort is the only meaningful cost; the scan after it is linear.

Complexity

Time: $O(n log n)$ , driven by L1 (the sort).
Space: $O(n)$ for sorted(nums) (Python returns a new list). If you mutate in place with nums.sort(), it’s $O(log n)$ for the sort’s stack frames (Timsort).

Improvement: we dropped one order of growth. Worth knowing as an alternative when memory is tight and in-place sort is available.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        let sorted = nums.sorted()
        for index in 1..<sorted.count where sorted[index] == sorted[index - 1] { return true }
        return false
    }
}

Approach 3: Hash set (optimal)

Walk the array once, storing values in a set. The first repeat hit is a duplicate.

def contains_duplicate(nums: list[int]) -> bool:
    seen = set()                       # L1: O(1) empty set
    for x in nums:                     # L2: loop, n iterations
        if x in seen:                  # L3: O(1) avg set lookup
            return True                # L4: O(1) early return
        seen.add(x)                    # L5: O(1) avg set insert
    return False

function containsDuplicate(nums: number[]): boolean {
    const seen = new Set<number>();    // L1: O(1) empty set
    for (const x of nums) {            // L2: loop, n iterations
        if (seen.has(x)) return true;  // L3-L4: O(1) avg set lookup + early return
        seen.add(x);                   // L5: O(1) avg set insert
    }
    return false;
}

func containsDuplicate(nums []int) bool {
  seen := make(map[int]struct{})     // L1: O(1) empty map
  for _, x := range nums {           // L2: loop, n iterations
    if _, ok := seen[x]; ok {      // L3: O(1) avg map lookup
      return true                // L4: O(1) early return
    }
    seen[x] = struct{}{}           // L5: O(1) avg map insert
  }
  return false
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init set)	$O(1)$	1	$O(1)$
L2 (loop)	$O(1)$	n	$O(n)$
L3 (set lookup)	$O(1)$ avg	n	$O(n)$ ← dominates
L4 (return)	$O(1)$	at most 1	$O(1)$
L5 (set insert)	$O(1)$ avg	up to n	$O(n)$

Each iteration does constant-time hash operations. Single pass, $O(1)$ average per step.

Complexity

Time: $O(n)$ , driven by L3/L5 (hash operations per element).
Space: $O(n)$ . The set can hold up to all n values before a duplicate is found.

One-liner

Same complexity, more Pythonic:

def contains_duplicate(nums: list[int]) -> bool:
    return len(set(nums)) < len(nums)

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        var seen = Set<Int>()
        for value in nums where !seen.insert(value).inserted { return true }
        return false
    }
}

Summary

Approach	Time	Space
Brute force (every pair)	$O(n²)$	$O(1)$
Sort + adjacent check	$O(n log n)$	$O(n)$ (or $O(log n)$ in-place)
Hash set	$O(n)$	$O(n)$

The hash-set approach is strictly best on time. Use the sort variant only when memory is constrained and you can sort in place.

Test cases

# Quick smoke tests, paste into a REPL or save as test_contains_duplicate.py and run.
# Uses the canonical implementation (Approach 3: hash set).

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

def _run_tests():
    assert contains_duplicate([1, 2, 3, 1]) == True
    assert contains_duplicate([1, 2, 3, 4]) == False
    assert contains_duplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]) == True
    assert contains_duplicate([]) == False
    assert contains_duplicate([5]) == False
    assert contains_duplicate([5, 5]) == True
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function containsDuplicate(nums: number[]): boolean {
    const seen = new Set<number>();
    for (const x of nums) {
        if (seen.has(x)) return true;
        seen.add(x);
    }
    return false;
}

console.assert(containsDuplicate([1, 2, 3, 1]) === true);
console.assert(containsDuplicate([1, 2, 3, 4]) === false);
console.assert(containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]) === true);
console.assert(containsDuplicate([]) === false);
console.assert(containsDuplicate([5]) === false);
console.assert(containsDuplicate([5, 5]) === true);
console.log("all tests pass");

package main

import "fmt"

func containsDuplicate(nums []int) bool {
  seen := make(map[int]struct{})
  for _, x := range nums {
    if _, ok := seen[x]; ok { return true }
    seen[x] = struct{}{}
  }
  return false
}

func main() {
  if !containsDuplicate([]int{1, 2, 3, 1})           { panic("test 1") }
  if containsDuplicate([]int{1, 2, 3, 4})             { panic("test 2") }
  if !containsDuplicate([]int{1, 1, 1, 3, 3, 4, 3, 2, 4, 2}) { panic("test 3") }
  if containsDuplicate([]int{})                       { panic("test 4") }
  if containsDuplicate([]int{5})                      { panic("test 5") }
  if !containsDuplicate([]int{5, 5})                  { panic("test 6") }
  fmt.Println("all tests pass")
}

Arrays, input container
Hash Tables, set membership for $O(1)$ dedup (optimal)

Array Scans, the linear pass habit of carrying just enough state while reading each item once.
Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.

217. Contains Duplicate (Easy)

Problem

Try it yourself

Approach 1: Brute force, check every pair

Approach 2: Sort and compare adjacent

Approach 3: Hash set (optimal)

One-liner

Summary

Test cases

Related data structures

Related concepts