217. Contains Duplicate

Problem¶

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 it interesting?¶

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

Python solution¶

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

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

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

        return False

Comment on 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