Sweaty Imposter

Contains Duplicate

EasyArrays & HashingBlind 75JuniorOpen on LeetCodeUpdated

You're given an integer array nums. Return true if any value appears at least twice anywhere in the array, and false if every element is distinct. The repeated values don't have to be next to each other, and you only report whether a repeat exists, not which value it is.

Examples

nums = [1,2,3,1] returns true

The value 1 appears at index 0 and again at index 3.

nums = [1,2,3,4] returns false

All four values are different, so nothing repeats.

nums = [1,1,1,3,3,4,3,2,4,2] returns true

Several values repeat. The first repeat shows up at index 1, where a second 1 appears.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Hints

Hint 1

As you read each number, you need to know whether it has already shown up. What lets you answer that instantly?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Scan the array while remembering every value seen so far in a hash set. Before adding a value, check whether it's already in the set: if it is, you've found a duplicate and can return true right away. If the loop finishes, every value was new. Set lookups and inserts are O(1) on average, so one pass is enough. Sorting and comparing neighbors also works, in O(n log n) time without the set.

Time

O(n)

Space

O(n)

Pitfall

Comparing every pair is O(n^2) and times out at 10^5 elements. Comparing only neighbors without sorting first misses repeats that are far apart, like the two 1s in [1,2,3,1].

Solutions

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