217. Contains Duplicate - Explanation

Problem Link

Description

Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

Example 1:

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

Output: true

Example 2:

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

Output: false


Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.


Hint 1

A brute force solution would be to check every element against every other element in the array. This would be an O(n^2) solution. Can you think of a better way?


Hint 2

Is there a way to check if an element is a duplicate without comparing it to every other element? Maybe there's a data structure that is useful here.


Hint 3

We can use a hash data structure like a hash set or hash map to store elements we've already seen. This will allow us to check if an element is a duplicate in constant time.


Company Tags

Google7 Amazon6 Meta4 Microsoft4 Bloomberg2 Netflix3 TCS2 Apple8 Yahoo8 Adobe7 Uber7 Oracle3 Accenture3 J.P. Morgan2 IBM2 Zoho2 DE Shaw2


1. Brute Force

Intuition

We can check every pair of different elements in the array and return true if any pair has equal values.
This is the most intuitive approach because it directly compares all possible pairs, but it is also the least efficient since it examines every combination.

Algorithm

  1. Iterate through the array using two nested loops to check all possible pairs of distinct indices.
  2. If any pair of elements has the same value, return true.
  3. If all pairs are checked and no duplicates are found, return false.
class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(1)O(1)

2. Sorting

Intuition

If we sort the array, then any duplicate values will appear next to each other.
Sorting groups identical elements together, so we can simply check adjacent positions to detect duplicates.
This reduces the problem to a single linear scan after sorting, making it easy to identify if any value repeats.

Algorithm

  1. Sort the array in non-decreasing order.
  2. Iterate through the array starting from index 1.
  3. Compare the current element with the previous element.
  4. If both elements are equal, we have found a duplicate — return True.
  5. If the loop finishes without detecting equal neighbors, return False.
class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

Time & Space Complexity

  • Time complexity: O(nlog⁡n)O(n \log n)
  • Space complexity: O(1)O(1) or O(n)O(n) depending on the sorting algorithm.

3. Hash Set

Intuition

We can use a hash set to efficiently keep track of the values we have already encountered.
As we iterate through the array, we check whether the current value is already present in the set.
If it is, that means we've seen this value before, so a duplicate exists.
Using a hash set allows constant-time lookups, making this approach much more efficient than comparing every pair.

Algorithm

  1. Initialize an empty hash set to store seen values.
  2. Iterate through each number in the array.
  3. For each number:
    • If it is already in the set, return True because a duplicate has been found.
    • Otherwise, add it to the set.
  4. If the loop finishes without finding any duplicates, return False.
class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

4. Hash Set Length

Intuition

This approach uses the same idea as the previous hash set method: a set only stores unique values, so duplicates are automatically removed.
Instead of checking each element manually, we simply compare the length of the set to the length of the original array.
If duplicates exist, the set will contain fewer elements.
The logic is identical to the earlier approach — this version is just a shorter and more concise implementation of it.

Algorithm

  1. Convert the array into a hash set, which removes duplicates.
  2. Compare the size of the set with the size of the original array.
  3. If the set is smaller, return True because duplicates must have been removed.
  4. Otherwise, return False.
class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) < len(nums)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)