How do you solve Contains Duplicate on LeetCode?

Contains Duplicate (LeetCode #217) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a HashSet allows for efficient duplicate checking.

What is the brute force solution for Contains Duplicate?

The brute force approach for Contains Duplicate is Brute Force, with O(n²) time complexity and O(1) space complexity. We can check every pair of elements in the array to see if any two are the same. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Contains Duplicate?

Contains Duplicate uses the following concepts: Array, Hash Table, Sorting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Contains Duplicate?

Explain your thought process clearly as you code. Consider edge cases before finalizing your solution. Discuss time and space complexity with your interviewer.

What are common mistakes when solving Contains Duplicate?

Not considering edge cases like an array with only one element. Forgetting to return false if no duplicates are found.

#217

Contains Duplicate

Easy

ArrayHash TableSortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a HashSet allows us to track the elements we have seen so far, making it easy to check for duplicates in a single pass through the array.

⚙️

Algorithm

5 steps

1Step 1: Initialize an empty HashSet.
2Step 2: Loop through each element in the array.
3Step 3: For each element, check if it is already in the HashSet. If it is, return true.
4Step 4: If it is not in the HashSet, add it to the HashSet.
5Step 5: If the loop completes without finding duplicates, return false.

solution.py7 lines

1def containsDuplicate(nums):
2    seen = set()
3    for num in nums:
4        if num in seen:
5            return True
6        seen.add(num)
7    return False

ℹ

Complexity note: The time complexity is O(n) because we only pass through the array once. The space complexity is O(n) due to the HashSet storing up to n elements in the worst case.

1Using a HashSet allows for efficient duplicate checking.
2Brute force is simple but not practical for large inputs.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.