Contains Duplicate

Difficulty: Easy | Acceptance: 64.30% | Paid: No Topics: Array, Hash Table, Sorting

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

• Examples
• Constraints
• Brute Force
• Sorting
• Hash Set

Examples

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

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

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

Constraints

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

Brute Force

Intuition Compare every element with every other element to see if they are equal.

Steps

• Iterate through the array with index i.
• For each i, iterate through the array with index j starting from i + 1.
• If nums[i] == nums[j], return true.
• If loops finish without finding a duplicate, 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

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: This approach is inefficient for large arrays and will likely result in a Time Limit Exceeded error on LeetCode.

Sorting

Intuition If the array is sorted, any duplicate elements will be adjacent to each other.

Steps

• Sort the array in non-decreasing order.
• Iterate through the sorted array.
• If nums[i] == nums[i + 1], return true.
• If the loop finishes, 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

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on the sorting algorithm implementation.
• Notes: Modifies the original array. Faster than brute force but not the most optimal time complexity.

Hash Set

Intuition Use a hash set to keep track of elements we have seen so far. If we encounter an element already in the set, it is a duplicate.

Steps

• Initialize an empty hash set.
• Iterate through each number in the array.
• If the number is already in the set, return true.
• Otherwise, add the number to the set.
• If the loop finishes, 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

Complexity

• Time: O(n)
• Space: O(n)
• Notes: This is the optimal approach for time complexity, trading space for speed.