LeetCode 217: Contains Duplicate | Easy Way to Solve

LeetCode 217: Contains Duplicate is a popular introductory problem often asked in coding interviews (e.g., at Microsoft, Amazon, Google).

The Challenge:

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.

Here are the three most common ways to solve it, ranging from the most efficient to the most concise.

1. The Optimal Approach: Hash Set

This is the standard interview answer. You trade a little bit of memory for speed.

• Logic: Iterate through the array while storing numbers in a “visited” set. If you encounter a number that is already in the set, you have found a duplicate.

• Time Complexity: $O(n)$ — We scan the array once.

• Space Complexity: $O(n)$ — We store unique elements in the set.

Also Read : Mangago Not Working

Python

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

Java

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }
}

C++

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;
    }
};

2. The Python “One-Liner”

If you are writing production code or a quick script, this is the most “Pythonic” way. It compares the length of the list (which counts duplicates) to the length of the set (which removes duplicates).

• Logic: If the set is smaller than the list, duplicates must have been removed.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)

3. The “Space Saver” Approach: Sorting

If memory is extremely tight and you cannot afford $O(n)$ space for a set, you can sort the array first.

• Logic: Sort the numbers. Any duplicates will now be sitting next to each other (e.g., [1, 3, 2, 1] becomes [1, 1, 2, 3]). Iterate and check if nums[i] == nums[i+1].

• Time Complexity: $O(n \log n)$ — Sorting takes longer than a linear scan.

• Space Complexity: $O(1)$ or $O(\log n)$ — Depends on the sorting algorithm, but generally uses less memory than a set.

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

Quick Summary Table