Contains Duplicate

The machine must report whether any value appears more than once in an array of integers. The sorted-adjacency trick works, but sorting is O(n log n); the direct approach is a hash set with early exit. The insight: membership in a set is O(1) average, and the instant a second insert fails, the loop can stop — you don't need to finish the array.

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

Steps: (1) walk the array once, (2) test each value against the set, (3) return True on the first hit; if the pass completes, return False.

Time is O(n) average, O(n²) pathological if the set hash degrades — fine for contest input. Space is O(n) for the set.

Trickiest edge case: large inputs where the duplicate sits near the end — the worst case for both time (full pass) and space (the set holds nearly everything). The early exit is still correct there. Negative values and zeros hash normally; no special handling needed.