📖 5 min read
Last updated on

Contains Duplicate — Coding Interview Walkthrough

By intervu.dev

Hero Image for Contains Duplicate — Coding Interview Walkthrough

You’re in a coding interview. The interviewer says: “Given an integer array, return true if any value appears at least twice.” Contains Duplicate looks trivial. It’s LeetCode #217, and it appears in nearly every screening round — not because the code is hard, but because the conversation is. How many approaches do you know? Can you compare them? Can you explain the trade-off between time and space without being prompted? That’s what this problem is actually testing.

The Problem

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

(LeetCode #217)

Example 1

Input nums = [1, 2, 3, 1]

Output true

Example 2

Input nums = [1, 2, 3, 4]

Output false

Example 3

Input nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]

Output true

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

SkillWhat Interviewers Observe
Hash set intuitionDo you immediately recognize this as an O(1) lookup problem?
Trade-off articulationCan you compare sorting vs. hash set and choose deliberately?
Early exitDo you return as soon as a duplicate is found, or scan the entire array?
Edge case awarenessEmpty arrays, single-element arrays, large inputs with all duplicates
Follow-up readinessCan you extend this to “find duplicate within k distance”?

Step 1: Clarifying Questions

1. Can the array be empty or have one element? Both return false — no duplicate possible. Confirms you handle base cases.

2. Are the integers bounded? If values fit in a limited range, you might use a boolean array instead of a hash set. Usually not relevant for this problem but shows range-based thinking.

3. Can values be negative? Yes. A hash set handles this naturally; a fixed array approach would not.

4. Is there a space constraint? This opens the sorting alternative (O(1) extra space vs. O(n) for the set).

Step 2: A First (Non-Optimal) Idea

Compare every pair:

def containsDuplicate_brute(nums: list[int]) -> bool:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return True
    return False

O(n²) time, O(1) space. Correct but too slow for large inputs.

Step 3: The Key Insight

Duplicate detection is a membership problem. The question “have I seen this number before?” is answered in O(1) by a hash set. Add each number as you scan — if it’s already in the set, you’ve found a duplicate. This gives O(n) time with O(n) space, which is the standard trade-off for fast lookup.

Step 4: Optimal Strategy

Option A — Hash Set (O(n) time, O(n) space):

  1. Initialize an empty set.
  2. For each number, check if it’s already in the set.
  3. If yes, return True. If no, add it.
  4. Return False after the loop.

Option B — Sort first (O(n log n) time, O(1) space):

  1. Sort the array.
  2. Scan adjacent pairs — if any are equal, return True.
  3. Return False.

Python Implementation

def containsDuplicate(nums: list[int]) -> bool:
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

One-liner alternative:

def containsDuplicate(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))

The one-liner is clean but always processes the full array. The loop version returns early on first duplicate found — better in practice when duplicates appear early.

Sorting approach (O(1) extra space):

def containsDuplicate(nums: list[int]) -> bool:
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Note: this modifies the input array — worth flagging in an interview.

Time & Space Complexity

ApproachTimeSpace
Brute forceO(n²)O(1)
Hash setO(n)O(n)
SortO(n log n)O(1) extra

Common Interview Mistakes

  1. Using the brute force without recognizing it’s O(n²). Always state complexity before the interviewer asks.

  2. Using the one-liner without mentioning early exit. set(nums) builds the full set regardless. If a duplicate appears at index 1 of a million-element array, the loop is vastly faster.

  3. Sorting without noting it modifies the input. In-place sort changes the caller’s data — worth mentioning even if it’s acceptable here.

  4. Not discussing the time/space trade-off. The interviewer almost always wants to hear you compare approaches. “I’ll use a hash set for O(n) time at the cost of O(n) space. If space is constrained, sorting gives O(n log n) with O(1) extra” is a model answer.

  5. Not asking about the follow-up. Contains Duplicate II (within k distance) is a natural follow-up. Showing awareness of it signals interviewer-level problem thinking.

What a Strong Candidate Sounds Like

“I’ll use a hash set. As I scan the array, I check if the current element is already in the set — if yes, return true. If no, add it and continue. That’s O(n) time and O(n) space. If space is a concern, I could sort first and check adjacent pairs — O(n log n) time but only O(1) extra space. I’ll go with the hash set since speed is usually preferred unless told otherwise.”

Example Interview Dialogue

Interviewer: What if I wanted to know if any duplicate appears within k positions of another?

Candidate: That’s Contains Duplicate II. I’d use a sliding window hash set of size k. As I scan, I add each element to the set and remove the element k positions before the current index. If the current element is already in the set, it’s within k distance — return true. Same O(n) time, O(k) space.

Interviewer: What does len(nums) != len(set(nums)) do?

Candidate: It converts the array to a set — which drops duplicates — then compares sizes. If the set is smaller, a duplicate existed. It’s concise but always scans the whole array. My loop version returns early, which is better when duplicates are common or the array is large.

  • Contains Duplicate II (LeetCode #219). Find duplicates within k index distance — sliding window extension.
  • Contains Duplicate III (LeetCode #220). Duplicates within k distance AND value difference within t — sorted set approach.
  • Find the Duplicate Number (LeetCode #287). Find the duplicate in an array where you can’t use extra space — Floyd’s cycle detection.
  • Happy Number (LeetCode #202). Uses a set to detect cycles — same membership-check pattern.

From the Intervu walkthrough collection:

Practice This in a Mock Interview

Contains Duplicate is a problem where the code is easy but the conversation is what matters. Interviewers want to hear you name multiple approaches, compare trade-offs, and choose deliberately. That fluency only comes from practice.

Start a mock interview for Contains Duplicate on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →