Contains Duplicate

Given an array, determine whether any value appears more than once.

EasyRecommendedHashing

Solve This Problem

Video Solution

Video coming soon

We're producing a video walkthrough — check back soon.

Problem Overview

Given an array, determine whether any value appears more than once.

Why solve this?

The simplest possible hash-set membership check — it isolates Two Sum's core habit (remember what you've already seen) from the extra bookkeeping of also matching a target sum.

Pattern Recognition

Any 'has this been seen before' question over a single array is a hash-set membership check, not a nested-loop comparison.

Prerequisites

Two Sum — this problem strips Two Sum's hash-map idea down to its simplest form: just remembering what's been seen.

Hints

A nested loop comparing every pair works but is O(n^2) — you can do better.
A hash set lets you check whether a value has been seen before in O(1) on average.
You can also sort the array first and scan for adjacent equal values, trading time for no extra space.

Approach

Walk the array once while keeping a hash set of every value seen so far. Before inserting the current value, check whether it's already in the set — if it is, a duplicate exists and you can return immediately. If the scan finishes with no match found, every value was unique.

Code

Solution.java

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (!seen.add(num)) {
                return true;
            }
        }
        return false;
    }
}

Time: O(n) averageSpace: O(n)