Big O Practice: Contains Duplicate

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

Variables

• n - length of the input array nums

Explanation

One pass with O(1) set membership and insertion - **O(n)** time. The set holds up to `n` elements in the worst case, **O(n)** space. The naive nested-loop alternative is O(n²); the hash set buys linearity.

More Big O practice problems · Today's daily problem