{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Contains Duplicate – Solution & Complexity

Interview solutions
/
Contains Duplicate

1. Understand the Problem

  • We need to decide whether any value appears more than once.
  • The exact duplicate value does not need to be returned, only True or False.
  • An empty or fully distinct list should return False.

2. Consider the Brute Force Idea

  • A direct approach compares every pair of numbers.
  • If any pair has the same value, we found a duplicate.
  • This works, but checking all pairs takes O(n²) time.
def contains_duplicate(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

3. Use a Set for Fast Lookups

  • A set can tell us in average O(1) time whether we have seen a number before.
  • Scan the array once from left to right.
  • When a number is already in the set, return True immediately.

4. Build the Check Incrementally

  • Keep a seen set.
  • For each number, check membership before adding it.
  • If the loop finishes, every number was distinct.
def contains_duplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

5. Final Solution and Complexity

  • The final solution returns as soon as a duplicate is found.
  • Time complexity is O(n) because each element is processed once.
  • Space complexity is O(n) in the worst case for the set of seen values.
def contains_duplicate(nums: list[int]) -> bool:
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

FAQ

See also:

Practice Contains Duplicate online (run code in the browser)Majority Element solution (easy)Two Sum solution (easy)Best Time to Buy and Sell Stock solution (easy)Binary Search solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?