Introduction to the Contains Duplicate Problem
The "Contains Duplicate" problem is one of the most fundamental algorithmic challenges you'll encounter in coding interviews and competitive programming. At its core, the problem asks a simple question: given an array of integers, does any value appear at least twice? While the question itself is straightforward, the way you choose to solve it reveals a great deal about your understanding of time and space complexity trade-offs.
In this tutorial, we'll walk through multiple approaches to solving the Contains Duplicate problem in JavaScript, starting from the naive solution and progressing to the most optimal one. By the end, you'll understand not only how to solve this specific problem but also the broader patterns that apply to similar array and hash-based challenges.
Problem Statement
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.
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
Why This Problem Matters
You might wonder why such a seemingly simple problem is worth studying. The truth is, Contains Duplicate is a gateway problem that introduces several critical concepts:
- Hash-based lookups: Learning when and how to use a Set or Map for O(1) lookups.
- Complexity analysis: Understanding the difference between O(n²) and O(n) solutions and why it matters at scale.
- Sorting as a tool: Recognizing when sorting can simplify a problem by bringing duplicates adjacent to each other.
- Interview readiness: This problem frequently appears on platforms like LeetCode and in technical interviews at major companies.
Mastering this problem builds the foundation for more complex challenges like Contains Duplicate II, Contains Duplicate III, and group anagram problems that rely on similar hashing techniques.
Approach 1: The Brute Force Solution
The most intuitive approach is to compare every element with every other element. If any two elements are equal, we return true. If we finish all comparisons without finding a match, we return false.
Implementation
function containsDuplicateBruteForce(nums) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] === nums[j]) {
return true;
}
}
}
return false;
}
// Example usage
console.log(containsDuplicateBruteForce([1, 2, 3, 1])); // true
console.log(containsDuplicateBruteForce([1, 2, 3, 4])); // false
Complexity Analysis
This solution has a time complexity of O(n²) because for each of the n elements, we potentially compare it with every other element. The space complexity is O(1) since we only use a couple of loop variables.
While this works for small arrays, it becomes prohibitively slow for large inputs. An array with 10,000 elements would require up to 50 million comparisons. This is why we need a better approach.
Approach 2: Sorting First
If we sort the array first, any duplicate values will end up adjacent to each other. Then we only need a single pass through the array, comparing each element with its neighbor.
Implementation
function containsDuplicateSorted(nums) {
// Create a copy to avoid mutating the original array
const sorted = [...nums].sort((a, b) => a - b);
for (let i = 0; i < sorted.length - 1; i++) {
if (sorted[i] === sorted[i + 1]) {
return true;
}
}
return false;
}
// Example usage
console.log(containsDuplicateSorted([1, 2, 3, 1])); // true
console.log(containsDuplicateSorted([1, 2, 3, 4])); // false
Complexity Analysis
Sorting in JavaScript typically runs in O(n log n) time, and the subsequent linear scan is O(n). The overall time complexity is therefore O(n log n). Space complexity depends on the sorting algorithm used by the engine, but it's generally O(log n) for the call stack in most implementations.
This is a significant improvement over the brute force approach, but we can do even better.
Approach 3: Using a Set (Optimal Solution)
The optimal solution leverages a JavaScript Set, which provides O(1) average-time complexity for insertions and lookups. As we iterate through the array, we check if the current element already exists in the Set. If it does, we've found a duplicate. If not, we add it to the Set and continue.
Implementation
function containsDuplicate(nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) {
return true;
}
seen.add(num);
}
return false;
}
// Example usage
console.log(containsDuplicate([1, 2, 3, 1])); // true
console.log(containsDuplicate([1, 2, 3, 4])); // false
console.log(containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2])); // true
Complexity Analysis
This solution runs in O(n) time because we traverse the array once, and each Set operation (both has and add) is O(1) on average. The space complexity is O(n) in the worst case, as we might store every element in the Set before finding a duplicate (or determining there are none).
This is the most efficient general-purpose solution and is what most interviewers expect to see.
Approach 4: The One-Liner Shortcut
JavaScript offers an elegant shortcut by comparing the size of a Set created from the array with the array's length. If the Set is smaller, duplicates must exist because Sets only store unique values.
Implementation
function containsDuplicateOneLiner(nums) {
return new Set(nums).size !== nums.length;
}
// Example usage
console.log(containsDuplicateOneLiner([1, 2, 3, 1])); // true
console.log(containsDuplicateOneLiner([1, 2, 3, 4])); // false
While concise and readable, this approach always processes the entire array, even if a duplicate is found early. The Set-based loop from Approach 3 can short-circuit and return true as soon as it finds the first duplicate, making it more efficient in cases where duplicates appear early in large arrays.
Best Practices
Choose the Right Approach for Your Context
For interviews and production code where performance matters, prefer the Set-based loop (Approach 3). It offers the best balance of readability and efficiency, with the added benefit of early termination.
Avoid Mutating Input Arrays
Notice that in the sorting approach, we created a copy of the array with [...nums] before sorting. Mutating input data can lead to subtle bugs, especially in larger codebases where the same array might be referenced elsewhere.
Handle Edge Cases Explicitly
function containsDuplicateRobust(nums) {
// Handle null, undefined, or non-array inputs
if (!Array.isArray(nums)) {
throw new TypeError('Input must be an array');
}
// An empty array or single-element array cannot have duplicates
if (nums.length <= 1) {
return false;
}
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) {
return true;
}
seen.add(num);
}
return false;
}
Consider Memory Constraints
If memory is extremely constrained and you cannot afford the O(n) space of a Set, the sorting approach (Approach 2) is a reasonable fallback. It uses less auxiliary space while still offering better-than-quadratic time complexity.
Use Meaningful Variable Names
In production code, prefer descriptive names like seenNumbers or visitedValues over generic names like set or s. This improves readability and maintainability for your fellow developers.
Performance Comparison
Let's compare the three main approaches side by side to understand the practical differences:
// Benchmark setup
const largeArray = Array.from({ length: 1000000 }, (_, i) => i);
largeArray.push(500000); // Add a duplicate at the end
console.time('Brute Force');
containsDuplicateBruteForce(largeArray);
console.timeEnd('Brute Force');
console.time('Sorting');
containsDuplicateSorted(largeArray);
console.timeEnd('Sorting');
console.time('Set');
containsDuplicate(largeArray);
console.timeEnd('Set');
On a typical machine, you'll observe that the brute force approach takes an extremely long time (potentially minutes), the sorting approach completes in a fraction of a second, and the Set approach is the fastest. If the duplicate is placed near the beginning of the array, the Set approach becomes even faster due to early termination.
Common Variations and Follow-Up Problems
Once you've mastered Contains Duplicate, you'll often encounter variations that build on the same foundations:
- Contains Duplicate II: Return true if there are two distinct indices i and j where nums[i] === nums[j] and the absolute difference between i and j is at most k. This requires a Map to track indices.
- Contains Duplicate III: A more complex variation involving value differences and index differences, often solved with a sliding window and balanced tree structure.
- Find All Duplicates in an Array: Instead of returning a boolean, return a list of all values that appear twice, often solvable in O(n) time and O(1) extra space using clever indexing tricks.
Understanding the core Set-based pattern from this tutorial will make tackling these variations significantly easier.
Conclusion
The Contains Duplicate problem is a perfect example of how a simple question can teach profound lessons about algorithm design. We started with a brute force O(n²) solution, improved to O(n log n) with sorting, and finally arrived at the optimal O(n) solution using a Set. Along the way, we explored trade-offs between time and space complexity, the importance of avoiding input mutation, and the value of early termination. By internalizing these patterns, you'll be well-equipped not only to solve this specific problem in interviews but also to recognize similar hashing opportunities across a wide range of algorithmic challenges. Remember that the best solution is not always the shortest one—choose the approach that best fits your specific constraints around performance, memory, and code clarity.