Week 1 · Arrays & Hashing

Contains Duplicate

Given a list of integers, decide whether any value appears at least twice. This is the smallest useful version of the seen-set pattern.

Easy Arrays & Hashing Week 1 Practice runner

Frame the problem

The input can contain positive, negative, and repeated integers.
You only need a boolean, not the duplicate value or all duplicates.
The first repeated value is enough to stop.

1. Reveal example inputs and outputs

Example 1

Input:

contains_duplicate([
  1,
  2,
  3,
  1
])

Output:

true

Example 2

Input:

contains_duplicate([
  1,
  2,
  3,
  4
])

Output:

false

2. Brute force first

What nested loop would compare every pair? Which comparison can a set answer in O(1) average time?

3. Reveal the insight ladder

Before reading index i, keep every earlier value in a set.
If nums[i] is already in the set, a duplicate exists.
If it is not present, add it and preserve the invariant for the next index.

4. Dry run before code

nums = [1, 2, 3, 1].
Seen after 1, 2, 3 is {1, 2, 3}.
The next 1 is already present, so return True.

5. Reveal final Python solution

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

Complexity: Time O(n) average, space O(n).

Interview narration

I only need to know whether a value appeared before.
A set is the smallest state that preserves that history.
I can return as soon as membership succeeds.

Common traps

Sorting works but costs O(n log n) and changes the shape of the reasoning.
Do not confuse duplicate values with duplicate indices.
Do not return True just because the list has length greater than one.

Follow-up drills

1. What if the interviewer asks for the duplicate value?

Return value instead of True at the first membership hit. The state stays the same.

2. What if memory must be O(1)?

For arbitrary integers, O(1) memory is not generally possible without changing the input or accepting slower sorting. If mutation is allowed, sorting in place can reduce extra memory but changes time to O(n log n).

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.