Contains Duplicate

Difficulty: Easy

Problem

Look through the integer array nums and report whether some number shows up more than once. Return true if there is a repeat and false if all the numbers are different.

Example

Input: nums = [4, 7, 9, 2, 7]
Output: true
Explanation: The value 7 appears at index 1 and again at index 4.

Brute-force approach

Compare every element with every other element to find duplicates.

Steps

  1. Pick each element
  2. Compare with all remaining elements
  3. If match found, return true
  4. If no matches, return false

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Checking every pair is slow
  • Redundant comparisons
  • Gets very slow with large arrays

Optimal approach

Key insight: A Set only stores unique values. If an element is already in the Set, it's a duplicate!

Use a Set to track seen elements - if we try to add a duplicate, we found one!

Steps

  1. Create an empty Set
  2. For each number, check if it's in the Set
  3. If yes, return true (duplicate found)
  4. If no, add it to the Set

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function containsDuplicate(nums):
    create empty set
    
    for each num in nums:
        if num exists in set:
            return true
        add num to set
    
    return false

Hints

  • Think about what data structure allows O(1) lookup
  • A Set stores unique values - what happens if you try to add a duplicate?

Complexity questions

Time complexity of comparing every pair?

O(n²). Comparing every element with every other = O(n²)

Space complexity of brute force?

O(1). Only loop variables, no extra storage needed.

Time complexity using a Set?

O(n). Single pass with O(1) Set add/lookup = O(n)

Space complexity using a Set?

O(n). Worst case: all n elements are unique, stored in Set.

Check your understanding of Contains Duplicate

What does the Contains Duplicate problem ask us to find?

Return true if any value appears at least twice. The problem asks us to check if ANY value appears at least twice and return true/false accordingly.

Given nums = [1, 2, 3, 4], what should be returned?

false. All elements are distinct (unique), so we return false - there are no duplicates.

Given nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2], what should be returned?

true. Multiple values appear more than once (1, 3, 4, 2), so we return true.

Related problems

Keep practising