{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Contains Duplicate – Solution & Complexity

Interview solutions
/
Contains Duplicate

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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
Learn the Arrays & Hashing pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Contains Duplicate online (run code in the browser)3Sum solution (medium)Group Anagrams solution (medium)Longest Consecutive Sequence solution (medium)Majority Element solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?