Contains Duplicate

Easy Arrays & Hashing Hash Set Lookup Original on LeetCode

Contains Duplicate is a easy arrays & hashing problem solved with the hash set lookup pattern. The best approach, optimal (hash set), runs in O(n) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

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

Examples

Example 1

Input
nums = [6, 2, 9, 2]
Output
true
Why
The value 2 appears at indices 1 and 3.

Example 2

Input
nums = [12, -3, 7, 0]
Output
false
Why
All four values are different.

Example 3

Input
nums = [5, 5, 5, 5, 5]
Output
true
Why
Every value repeats, so at least one repeats.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute forceO(n²)O(1)
Sort and compare neighboursO(n log n)O(n)
Optimal (hash set)O(n)O(n)

1Brute force

TimeO(n²)n(n - 1) / 2 pairs are checked in the worst case (no repeats).
SpaceO(1)Only two loop indices.

Compare every pair of positions and report a match as soon as one is found.

  1. For i from 0 to n - 1, for j from i + 1 to n - 1.
  2. If nums[i] == nums[j], return true.
  3. Return false.
class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

2Sort and compare neighbours

TimeO(n log n)Sorting dominates; the scan is linear.
SpaceO(n)The sorted copy (sorting in place would need only the sort's own stack, but it changes the caller's array).

Sort a copy of the array. Equal values become adjacent, so a single pass comparing each element with the one before it finds any repeat.

  1. Copy and sort the array.
  2. For i from 1 to n - 1, if a[i] == a[i - 1], return true.
  3. Return false.
class Solution {
    public boolean containsDuplicate(int[] nums) {
        int[] a = nums.clone();
        Arrays.sort(a);
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i - 1]) {
                return true;
            }
        }
        return false;
    }
}

3Optimal (hash set)

TimeO(n)One pass with O(1) average set operations.
SpaceO(n)The set can hold all n values when there is no repeat.

Walk the array once, adding each value to a hash set. If a value is already in the set when you reach it, you have found a repeat and can stop.

  1. Create an empty set.
  2. For each x in nums: if x is in the set, return true; otherwise add it.
  3. Return false.
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (!seen.add(x)) {
                return true;
            }
        }
        return false;
    }
}

Edge cases to test

  • A single element: nothing can repeat
  • The two equal values at the very start or the very end
  • Negative values and zero
  • Values at both ends of the range

Hints

Hint 1

Comparing every pair works but is quadratic. What changes if the array is sorted?

Hint 2

After sorting, equal values sit next to each other.

Hint 3

Or remember every value you have seen in a hash set; the first value already in the set is a repeat.

FAQ

What is the best time complexity for Contains Duplicate?

Optimal (hash set) runs in O(n) time and O(n) extra space. One pass with O(1) average set operations.

Which pattern does Contains Duplicate use?

It is a arrays & hashing problem that uses the hash set lookup pattern. Other problems with the same pattern: Longest Consecutive Sequence, Fair Candy Swap, Maximize Area of Square Hole in Grid.

Is there a brute force solution for Contains Duplicate?

Yes. Brute force takes O(n²) time and O(1) space. Compare every pair of positions and report a match as soon as one is found.

Which edge cases should I test for Contains Duplicate?

A single element: nothing can repeat; The two equal values at the very start or the very end; Negative values and zero; Values at both ends of the range.