☕ DSA Java Articles

Topics › Arrays › Easy

Contains Duplicate

Easy TUF ID 2392 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

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

Constraints (LeetCode 217): 1 ≤ nums.length ≤ 10^5, -10^9 ≤ nums[i] ≤ 10^9. The methods below also accept an empty array (answer false) and the full int range.

Example 1

nums = [1, 2, 3, 1]
answer = true        // 1 appears at index 0 and index 3

Example 2

nums = [1, 2, 3, 4]
answer = false       // all four values are different

The question is a yes/no question about the whole array, so every approach can stop at the first repeat it finds. The interesting part is how much work it takes to notice a repeat, and what that costs in memory.

Approach 1: Brute force

Intuition. A duplicate is a pair of positions i < j with nums[i] == nums[j]. The direct way to find one is to check every pair. Starting the inner loop at i + 1 ensures we never compare an element with itself and never check a pair twice.

Algorithm.

  1. For every i from 0 to n - 1:
  2. For every j from i + 1 to n - 1: if nums[i] == nums[j], return true.
  3. Return false if no pair matched.
static boolean bruteForce(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;
}

Complexity. Time O(n^2): up to n(n - 1)/2 comparisons when all values are distinct, which is exactly when we cannot stop early. Space O(1).

For n = 10^5 that is about 5 × 10^9 comparisons, far too slow. The waste is that each comparison tells us only about one pair; we never reuse what earlier comparisons taught us.

Approach 2: Better, sort and compare neighbours

Intuition. After sorting, equal values sit next to each other. So the array has a duplicate exactly when some adjacent pair is equal, and that check is a single linear pass. Sorting does the “grouping” work for us in O(n log n).

The method sorts a copy. Mutating a caller’s array to answer a yes/no question is a nasty side effect; if the caller does not need the original order you can sort in place and get O(1) extra space (apart from the sort’s own stack).

Algorithm.

  1. Copy nums and sort the copy.
  2. For i from 1 to n - 1: if a[i] == a[i - 1], return true.
  3. Return false.
static boolean better(int[] nums) {
    int[] a = nums.clone();                                  // do not reorder the caller's array
    Arrays.sort(a);
    for (int i = 1; i < a.length; i++) {
        if (a[i] == a[i - 1]) return true;
    }
    return false;
}

Complexity. Time O(n log n) for the sort; the scan is O(n). Space O(n) for the copy (or O(log n) sorting in place, since Arrays.sort on int[] is a dual-pivot quicksort).

Why it is correct. If two equal values exist, sorting places them in one contiguous block, so the first two elements of that block are neighbours. Conversely, two equal neighbours are a duplicate by definition.

Approach 3: Optimal, hash set

Intuition. Walk the array once and remember every value seen so far in a HashSet. When we reach a value that is already in the set, it occurred earlier, so we have a duplicate. Java’s Set.add returns false when the element was already present, which gives the check and the insert in one call.

Algorithm.

  1. Create an empty HashSet<Integer> seen.
  2. For each x in nums: if seen.add(x) returns false, return true.
  3. Return false.
static boolean optimal(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) {
        if (!seen.add(x)) return true;                       // add() returns false when x is already present
    }
    return false;
}

Dry run on nums = [1, 2, 3, 1]:

x seen before add(x) returns action
1 {} true continue
2 {1} true continue
3 {1, 2} true continue
1 {1, 2, 3} false return true

Complexity. Time O(n) on average: each add is O(1) expected. Space O(n) for the set in the worst case (all distinct).

Trade-offs worth knowing. The hash set is asymptotically fastest, but each Integer is a boxed object, so for 10^5 elements it uses several megabytes and has real constant-factor overhead. In practice the sort-based method is often competitive for arrays of this size, and it is the right choice when memory is tight. If the values come from a small known range (say 0..10^6), a boolean[] indexed by value is both O(n) and cheaper than a hash set. A one-line alternative, Arrays.stream(nums).distinct().count() < nums.length, is correct but always processes the entire array and cannot stop at the first repeat.

Edge cases and pitfalls