ToolMight LogoToolMight
EasyArrays & HashingPattern: Hash SetPattern: Sorting ScanPattern: Frequency Tracking

Contains Duplicate

Determine if any value appears at least twice in an integer array. A foundational problem for mastering constant-time hash lookups vs sorting trade-offs.

Problem Statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Examples & Constraints

Example 1
Input: nums = [1, 2, 3, 1]
Output: true
Explanation: The element 1 occurs at index 0 and index 3, satisfying the duplicate condition.
Example 2
Input: nums = [1, 2, 3, 4]
Output: false
Explanation: All elements are pairwise distinct, so no duplicates exist.
Constraints
  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Select Approach (2 Solutions)

Hash Set (Early Termination Lookup)

Optimal Approach
Time:O(n)
Space:O(n)

Iterate through elements while inserting them into a hash set. If an element already exists, immediately return true in O(1) average time.

Time ComplexityO(n)

We make at most a single pass over the array of N elements. Hash table lookups and insertions operate in O(1) average time.

Space ComplexityO(n)

In the worst case (when all elements are unique), the hash set stores all N numbers.

Underlying algorithmic logic

The Core Mental Model: Instant Memory Lookback

When scanning an array sequentially, the naive human approach is to look ahead and compare every item with everything else. In software engineering, that forward scan leads to an unacceptable O(n²) nested loop.

Instead, we invert the question: "Have I seen this specific integer already?"

A Hash Set gives us average O(1) lookup and insertion:

  1. Initialize an empty hash set seen.
  2. For each number num in nums:
  • If num is already present in seen, return true immediately (early exit).
  • Otherwise, insert num into seen.
  1. If the loop completes without finding any repeated item, return false.

Engineering Trade-Off: Time vs Memory

This approach trades auxiliary memory (up to N items stored in a hash bucket table) to achieve lightning-fast linear O(n) runtime. For interview discussions, mention that if memory is strictly constrained (e.g. microcontrollers or embedded memory limits), in-place sorting avoids the O(n) allocation.

Step-by-step execution walkthrough

1
Inspect nums[0] = 1

Check hash set. 1 is not in set. Add 1 to set.

set = {1}
2
Inspect nums[1] = 2

Check hash set. 2 is not in set. Add 2 to set.

set = {1, 2}
3
Inspect nums[2] = 3

Check hash set. 3 is not in set. Add 3 to set.

set = {1, 2, 3}
4
Inspect nums[3] = 1

Check hash set. 1 ALREADY exists in set! Immediate collision detected.

Collision: 1 found -> return true
Advantages
  • •Optimal O(n) runtime
  • •Early exit terminates as soon as first duplicate is spotted
Trade-offs
  • •Consumes O(n) auxiliary heap memory for hash table buckets

Code Implementations

Copy & paste production-ready solutions for Hash Set (Early Termination Lookup) in your language of choice

File: solution.py
Python
def contains_duplicate(nums: list[int]) -> bool:
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False
if __name__ == "__main__":
    test1 = [1, 2, 3, 1]
    test2 = [1, 2, 3, 4]
    print("test1 contains duplicate:", contains_duplicate(test1))
    print("test2 contains duplicate:", contains_duplicate(test2))
Interactive visualizer available

Understand Hash Table Visually

Visualize key hashing functions, index mapping arrays, and hash collision resolution techniques. Test live edge cases and watch memory state transitions step-by-step.

Launch Hash Table Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Valid Anagram

Determine whether two strings have the exact same character frequencies. A core problem demonstrating the power of fixed-size frequency buckets over O(n log n) sorting.

2 approaches(O(n))
Learn logic
MediumArrays & Hashing
Visualizer

Product of Array Except Self

Return an array where output[i] is the product of all elements in nums except nums[i], without using the division operation in O(n) time.

1 approach(O(n))
Learn logic