Skip to main content
CodePeetCodePeet
CodePeet 250

Contains Duplicate

EASYProblemSolveExternal Links

Description

Given an integer array nums, determine whether any value appears at least twice in the array.

Return true if any duplicate exists, and false if every element is distinct.

In other words, you need to check if all the numbers in the array are unique. If even one number repeats, the answer is true.

Examples

Example 1

Input: nums = [1, 2, 3, 1]

Output: true

Explanation: The value 1 appears at index 0 and again at index 3. Since 1 occurs more than once, the array contains a duplicate.

Example 2

Input: nums = [1, 2, 3, 4]

Output: false

Explanation: Every element in the array is unique — 1, 2, 3, and 4 each appear exactly once. There are no duplicates.

Example 3

Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]

Output: true

Explanation: Multiple values repeat: 1 appears three times, 3 appears three times, 4 appears twice, and 2 appears twice. Since at least one value is duplicated, the answer is true.

Constraints

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

Editorial

Brute Force

Intuition

The simplest way to check for duplicates is to compare every element with every other element. For each number in the array, we look at all the numbers that come after it and check if any of them are the same.

Think of it like a classroom roll call. You read out each student's name and ask everyone who hasn't been called yet: 'Does anyone else have this same name?' If you find a match at any point, you know there is a duplicate. If you go through the entire list without finding a match, all names are unique.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 1]:

Step 1: Fix i=0 (value 1). Compare with all elements after it.

Step 2: Compare nums[0]=1 with nums[1]=2. Are they equal? No (1 ≠ 2). Move to the next pair.

Step 3: Compare nums[0]=1 with nums[2]=3. Are they equal? No (1 ≠ 3). Move to the next pair.

Step 4: Compare nums[0]=1 with nums[3]=1. Are they equal? Yes (1 == 1)! We found a duplicate.

Step 5: Return true immediately — no need to check further.

Note: If we had nums = [1, 2, 3, 4], we would exhaust all pairs (6 total comparisons) and find no match, returning false.

Brute Force — Comparing Every Pair — Watch how we fix each element and compare it with every subsequent element. As soon as a match is found, we return true.

Algorithm

  1. For each index i from 0 to n-2:
    • For each index j from i+1 to n-1:
      • If nums[i] == nums[j], return true.
  2. If no duplicate was found after all comparisons, return false.

Code

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
};
class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j]:
                    return True
        return False
class Solution {
    public boolean containsDuplicate(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times, and the inner loop runs up to n-1 times for each outer iteration. The total number of comparisons is n*(n-1)/2, which is O(n²). In the worst case (all elements distinct), every pair is checked.

Space Complexity: O(1)

We only use two loop variables (i and j). No extra data structures are needed, so space usage is constant regardless of input size.

Why This Approach Is Not Efficient

The brute force approach checks all O(n²) pairs. With n up to 10^5, this results in approximately 5 × 10^9 comparisons — far too slow for typical time limits of 1-2 seconds.

The inefficiency stems from redundant comparisons. Each element is compared with every other element, but we are not leveraging any structure or organization in the data.

Key insight: if we sort the array first, duplicate elements will be placed right next to each other. Then we only need to compare adjacent elements — a single linear scan — rather than comparing every pair. Sorting costs O(n log n), and the subsequent scan costs O(n), giving us O(n log n) overall, which is a massive improvement over O(n²).

Better Approach - Sorting

Intuition

If we sort the array, all identical values will end up right next to each other. After sorting, we just need to walk through the array once and check if any two consecutive elements are the same.

Think of organizing a deck of cards by number. Once sorted, all the 7s are together, all the Kings are together, and so on. To find duplicates, you simply flip through the sorted deck and check if any card matches the one right after it.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 1]:

Step 1: Sort the array.

  • Original: [1, 2, 3, 1]
  • Sorted: [1, 1, 2, 3]
  • Notice how the two 1s are now adjacent.

Step 2: Compare sorted[0]=1 with sorted[1]=1.

  • Are they equal? Yes (1 == 1)!

Step 3: Duplicate found — return true immediately.

For a non-duplicate example, nums = [1, 2, 3, 4]:

Step 1: Sort: [1, 2, 3, 4] (already sorted).

Step 2: Compare sorted[0]=1 with sorted[1]=2. Not equal.

Step 3: Compare sorted[1]=2 with sorted[2]=3. Not equal.

Step 4: Compare sorted[2]=3 with sorted[3]=4. Not equal.

Step 5: All adjacent pairs checked, no match found. Return false.

Sorting Approach — Sort Then Scan Adjacent Pairs — Watch how sorting brings duplicate values together. After sorting, we only need to compare each element with its neighbor to detect duplicates.

Algorithm

  1. Sort the array in non-decreasing order.
  2. Iterate through the sorted array from index 0 to n-2:
    • Compare each element with the next element.
    • If sorted[i] == sorted[i+1], return true.
  3. If no adjacent pair matched, return false.

Code

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < (int)nums.size() - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
};
class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return True
        return False
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting the array dominates the time cost. Modern sorting algorithms (like Timsort in Python and Java, or Introsort in C++) run in O(n log n) time. The subsequent linear scan through adjacent pairs takes O(n), which is absorbed by the sorting cost. Total: O(n log n).

Space Complexity: O(1) to O(n)

The space depends on the sorting implementation. In-place sorting (like C++ std::sort) uses O(log n) space for recursion. Python's sort and Java's Arrays.sort use O(n) auxiliary space. If we sort in-place without creating a new array, the extra space is O(log n).

Why This Approach Is Not Efficient

The sorting approach runs in O(n log n) time, which is a big improvement over O(n²). However, it has two drawbacks:

  1. It modifies the input array. Sorting rearranges the elements, which may not be acceptable if the original order needs to be preserved. Making a copy adds O(n) space.

  2. O(n log n) is not the best we can do. The sorting step is a bottleneck. We are sorting the entire array just to detect adjacency, but we don't actually need the elements in order — we just need to know if any value has been seen before.

Key insight: a hash set can check membership in O(1) average time. If we iterate through the array and check whether each element is already in the set, we can detect duplicates in O(n) time — no sorting needed.

Optimal Approach - Hash Set

Intuition

Instead of comparing every pair or sorting the array, we can use a hash set to remember which values we have already encountered. As we scan through the array from left to right, for each element we ask: 'Have I seen this value before?' If the answer is yes, we have found a duplicate. If not, we add it to the set and move on.

Think of it like a guest list at a party. As each guest arrives, you check the list: 'Is this name already here?' If yes, you've found a repeat visitor. If no, you write the name down and welcome the next guest. The check and the write are both nearly instant because the list is organized for fast lookup (like a hash set).

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 1]:

Step 1: Initialize an empty hash set: seen = {}.

Step 2: Process nums[0] = 1.

  • Is 1 in seen? No (set is empty).
  • Add 1 to seen. seen = {1}.

Step 3: Process nums[1] = 2.

  • Is 2 in seen? No (set has {1}).
  • Add 2 to seen. seen = {1, 2}.

Step 4: Process nums[2] = 3.

  • Is 3 in seen? No (set has {1, 2}).
  • Add 3 to seen. seen = {1, 2, 3}.

Step 5: Process nums[3] = 1.

  • Is 1 in seen? Yes! We found 1 in the set.

Step 6: Return true — the value 1 is a duplicate.

Hash Set — One-Pass Duplicate Detection — Watch how we build a hash set while scanning the array. For each element, we check if it already exists in the set. The moment we find a repeat, we stop.

Algorithm

  1. Create an empty hash set.
  2. For each element num in the array:
    • If num is already in the set, return true (duplicate found).
    • Otherwise, add num to the set.
  3. If the loop completes without finding a duplicate, return false.

Code

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> seen;
        for (int num : nums) {
            if (seen.count(num)) {
                return true;
            }
            seen.insert(num);
        }
        return false;
    }
};
class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once. Each hash set operation (lookup and insert) takes O(1) on average due to hashing. In the worst case (all unique elements), we perform n lookups and n insertions, giving O(n) total. This is optimal — we must examine every element at least once.

Space Complexity: O(n)

In the worst case (all elements are unique), the hash set stores all n elements. Each element takes O(1) space in the set, so total space is O(n). This is a classic time-space tradeoff: we use extra memory to achieve faster lookup.