Contains Duplicate: Hash Set, Sorting, and the Follow-Ups Interviewers Ask

"Contains Duplicate" looks like a warm-up, and it is. But interviewers use it to see how you talk about trade-offs, so it is worth having a clean answer ready.

The problem

Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.

Approach 1: Hash set (O(n) time, O(n) space)

Walk the array once and remember what you have seen. The moment you meet a value that is already in the set, you can stop.

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

The early return matters: on inputs with an early duplicate you finish long before reaching the end.

Approach 2: Sort first (O(n log n) time, O(1) extra space)

If memory is tight, sort in place and compare neighbors. Duplicates end up next to each other.

def contains_duplicate_sorted(nums):
   nums.sort()
   for i in range(1, len(nums)):
       if nums[i] == nums[i - 1]:
           return True
   return False

Mention that this mutates the input. If the caller needs the original order, you either copy (losing the space win) or ask whether mutation is allowed.

The one-liner, and why to explain it

return len(set(nums)) != len(nums)

It is correct and readable, but it always builds the full set, so it gives up the early exit. Saying that out loud shows you understand what the shortcut costs.

Follow-ups to expect

How to present it in an interview

Start with the hash set, state O(n) time and O(n) space, then offer sorting as the low-memory option and ask which constraint matters more. That two-minute exchange is usually what the interviewer is actually grading.

If you want practice talking through trade-offs like this under time pressure, I work on an AI tool for job interviews that helps with live coding and behavioral rounds (disclosure: I'm on the Linkjob AI team).

‍