Contains Duplicate: Set Pattern

Learning Outcome

After this lesson, you should be able to identify duplicate detection problems and solve them with a set in one pass.

Problem Statement

Given an integer array nums, return true if any value appears at least twice. Return false if all values are distinct.

Brute Force Approach

Compare every element with every later element. If any pair has equal values, return true.

This is simple but slow because it performs repeated comparisons, leading to O(n^2) time.

Optimized Approach

Use a set to store values already seen. During the scan, if the current value is already in the set, a duplicate exists.

This turns repeated pair checks into average O(1) membership checks.

Exact Pseudocode

seen = empty set
for value in nums:
  if value exists in seen:
    return true
  add value to seen
return false
  

Reference Code

class Solution:
    def containsDuplicate(self, nums):
        seen = set()

        for value in nums:
            if value in seen:
                return True
            seen.add(value)

        return False
  

Sample Dry Run

Complexity

Edge Cases

• Empty or single-element array should return false if allowed.
• Duplicate appears immediately, such as [1, 1].
• Large negative and positive values.

Interview Checklist

• Use a set when only existence matters.
• Return as soon as a duplicate is found.
• Do not sort if the prompt asks for linear time.

FAQs