Skip to content

217. Contains Duplicate

On LeetCode ->

Reformulated Question

Given a list of integers, return True if any number appears more than once, else return False.

Example:

nums = [1, 2, 3, 1] -> True   # 1 is repeated

Key Trick

Use a set to track seen values, or compare len(nums) with len(set(nums)).

Trap

  • Using Counter or sorting works, but is more work than needed.
  • Forgetting that one duplicate anywhere is enough to return True.
  • Sorting changes time complexity to \(O(n \log n)\) when \(O(n)\) is possible.

Why Is This Question Interesting?

It tests whether you recognize a simple hash-set pattern for duplicate detection in linear time.

Solution with Idiomatic Python

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        # If any value is duplicated, the set becomes smaller than the list.
        return len(nums) != len(set(nums))

Alternative with early return:

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        seen = set()

        for n in nums:
            if n in seen:
                return True
            seen.add(n)

        return False

Pytest Test

import pytest


@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([1], False),
        ([1, 2, 3, 4], False),
        ([1, 2, 3, 1], True),
        ([1, 1], True),
        ([0, -1, -2, -3], False),
        ([-1, 0, 2, -1], True),
        ([1, 1, 1, 3, 3, 4, 3, 2, 4, 2], True),
        (list(range(1000)), False),
        (list(range(999)) + [0], True),
    ],
)
def test_contains_duplicate(nums, expected):
    assert Solution().containsDuplicate(nums) == expected

Comment My Solution

  • Your Counter solution is correct.
  • It uses extra counting work you do not need, since the problem only asks whether a duplicate exists.
  • Prefer a set solution because it is shorter and more idiomatic here.
  • Counter(nums) is still \(O(n)\) time and \(O(n)\) space, but with more overhead than necessary.
import pytest

class SolutionCounter:
    def containsDuplicate(self, nums: list[int]) -> bool:
        # Your approach: correct, but more work than needed.
        freq = Counter(nums)
        for n in freq:
            if freq[n] > 1:
                return True
        return False

class Solution:
    # Implemented after reading comments from AI
    def containsDuplicate(self, nums: list[int]) -> bool:
        seen = set()
        for n in nums:
            if n in seen:
                return True
            seen.add(n)
        return False

@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([1, 2, 3, 4], False),
        ([1, 2, 3, 1], True),
        ([1, 1, 1, 3, 3, 4, 3, 2, 4, 2], True),
    ],
)
def test_containsDuplicate(nums, expected):
    assert Solution().containsDuplicate(nums) == expected

Code

import pytest
from collections import Counter


class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        # Idiomatic solution: duplicates shrink the unique-value count.
        return len(nums) != len(set(nums))


class SolutionSeen:
    def containsDuplicate(self, nums: list[int]) -> bool:
        # Early-return variant using a set.
        seen = set()

        for n in nums:
            if n in seen:
                return True
            seen.add(n)

        return False


class SolutionCounter:
    def containsDuplicate(self, nums: list[int]) -> bool:
        # Your approach: correct, but more work than needed.
        freq = Counter(nums)
        for n in freq:
            if freq[n] > 1:
                return True
        return False


@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([1], False),
        ([1, 2, 3, 4], False),
        ([1, 2, 3, 1], True),
        ([1, 1], True),
        ([0, -1, -2, -3], False),
        ([-1, 0, 2, -1], True),
        ([1, 1, 1, 3, 3, 4, 3, 2, 4, 2], True),
        (list(range(1000)), False),
        (list(range(999)) + [0], True),
    ],
)
def test_contains_duplicate(nums, expected):
    assert Solution().containsDuplicate(nums) == expected
    assert SolutionSeen().containsDuplicate(nums) == expected
    assert SolutionCounter().containsDuplicate(nums) == expected


Solution().containsDuplicate([1, 2, 3, 4])
Solution().containsDuplicate([1, 2, 3, 1])
SolutionSeen().containsDuplicate([-1, 0, 2, -1])
SolutionCounter().containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2])