Contains Duplicate

1. The obvious way

   Compare every pair of numbers: O(n²). Or sort first and compare neighbours: O(n log n).

2. The key insight

   Keep an attendance sheet (a set). For each number: already on the sheet means a duplicate; otherwise add it. Looking something up in a set is one step, so the whole job is one walk through the list.

3. The algorithm
   1. Start with an empty sheet (a set).
   2. For each number: is it already on the sheet? Then answer True.
   3. Otherwise write it on the sheet.
   4. Reached the end with no repeat? Answer False.

Watch it run

sheet: {1}

def contains_duplicate(nums):
    sheet = set()                    # numbers already signed
    for number in nums:
        if number in sheet:
            return True              # someone signed twice
        sheet.add(number)
    return False

# one-liner idea: len(set(nums)) != len(nums)

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.