Contains Duplicate
(#217), Easy
Category: Array, Hash Table, Sorting
Problem Statement
Given an integer array `nums`, return `true` if any value appears **at least twice**, and `false` if every element is distinct. Your task is to detect the presence of duplicates in the array efficiently.
Examples
Input: nums = [1, 2, 3, 1]
Output: true
Explanation: '1' appears more than once.
Input: nums = [1, 2, 3, 4]
Output: false
Explanation: All elements are unique.
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Explanation: Multiple elements have duplicates.
Approach
Approach 1: Sorting-Based Duplicate Check
- Sort the array in ascending order.
- Iterate from index 0 to n-2 and compare each element with the next.
- If `nums[i] === nums[i + 1]`, return `true` (duplicate found).
- If loop completes with no duplicates, return `false`.
// 🔹 Approach: Sorting
var containsDuplicate = function (nums) {
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] === nums[i + 1]) {
return true;
}
}
return false;
};Approach 2: Hash Set for Constant-Time Lookup
- Create an empty Set to store seen numbers.
- Iterate through each element in `nums`.
- If the current number already exists in the Set, return `true`.
- Otherwise, add the number to the Set.
- If loop completes with no duplicates, return `false`.
// 🔹 Approach: Hash Set
var containsDuplicate = function (nums) {
const seen = new Set();
for (let num of nums) {
if (seen.has(num)) return true;
seen.add(num);
}
return false;
};Complexity
Time: O(n) – linear traversal with Set lookup
Space: O(n) – to store unique elements in Set