Contains Duplicate

Given a list of integers nums, decide whether any value occurs at two or more different positions.

Return true if some value is repeated anywhere in the list, and false if every element is distinct. The repeated copies do not need to be next to each other.

Aim for a solution that is faster than comparing every pair of elements.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

Pattern Path · Hashing & Counting · problem 6 of 169

Start simple

Compare every pair (i, j) with two nested loops: O(n²) time, O(1) space. Sorting and checking neighbours is O(n log n).

The key idea

A repeat means that, at some point while scanning left to right, we meet a value we have already met. So keep a hash set of the values seen so far. For each element, first check membership: if it is already in the set, we have found a duplicate and can return true immediately. Otherwise add it and continue. If the scan finishes, every value was new when we met it, so all are distinct.

Hash-set lookups and inserts take expected O(1) time, giving O(n) overall, and the early exit means lists with an early repeat finish quickly.

The alternative is to sort a copy and check adjacent elements, since equal values end up next to each other. That uses O(1) extra memory with an in-place sort but costs O(n log n) time and may modify the input, a trade-off worth mentioning to the interviewer.

Complexity

• Time: O(n)
• Space: O(n)

Python

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for x in nums:
            if x in seen:
                return True
            seen.add(x)
        return False

JavaScript

var containsDuplicate = function(nums) {
  const seen = new Set();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
};

What the interviewer is checking

A warm-up that checks whether you instinctively reach for a hash set and can articulate the time-versus-memory trade-off against sorting.

Mistakes to avoid

• Using a list instead of a set for "seen", which makes each lookup O(n) and the whole solution O(n²).
• Sorting the caller's list in place without mentioning that it mutates the input.
• Returning early with false inside the loop instead of only after it finishes.

Follow-ups to expect

• What if duplicates only count within distance k? (Sliding window set of size k.)
• What if memory is very tight? (Sort in place, compare neighbours.)
• What if the data is too big for one machine? (Hash-partition values, check each shard.)

In real software

Deduplicating events, detecting a reused ID or coupon code, and checking uniqueness constraints before a database insert all rely on a fast "seen before?" set.

Practice next