Contains Duplicate — Problem Statement & Solution Guide
Problem Description
Given an integer array nums, determine whether the array contains any repeated value. Return true if at least one element occurs two or more times; otherwise return false. The solution must examine the entire array and decide based solely on the presence of duplicates, without modifying the input order.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Contains Duplicate"
WHY DOES IT MATTER?
Detecting duplicates is a fundamental pattern for validating data integrity, preventing redundant processing, and ensuring uniqueness constraints in databases and caches.
OPTIMIZATION CHALLENGE
The key insight is to replace the O(n²) pairwise comparison with a constant‑time lookup structure, turning the problem into a membership test that can be resolved in a single traversal.
REAL-WORLD CONNECTION
In distributed caching systems like Redis, a duplicate key check prevents overwriting existing entries, similar to how a load balancer hashes requests to ensure the same client consistently reaches the same server.
During an interview, quickly write the hash‑set solution, then discuss edge cases (empty array, single element) and optionally mention the sorting alternative to demonstrate depth of understanding.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The "Contains Duplicate" problem is a classic illustration of the trade‑off between time and space in algorithm design. A naive solution that compares each element with every other runs in O(n²) time, which quickly becomes infeasible for large arrays because the number of pairwise checks grows quadratically. The optimal paradigm leverages a hash‑based set (or unordered_map) to achieve constant‑time membership checks, allowing the algorithm to scan the array once while remembering which values have already been seen. This approach transforms the problem into a single pass over the data, reducing the overall complexity to linear time while using linear extra space to store the unique elements encountered.
Interview Questions on This Problem
Q1How would you modify the solution if the array is read‑only and you cannot use extra space beyond O(1)?
You can sort a copy of the array (O(n log n) time, O(n) auxiliary space) and then scan for adjacent equal values, or use an in‑place sorting algorithm if mutation is allowed, achieving O(1) extra space but still O(n log n) time.
Q2What is the expected time complexity if the input numbers are bounded within a small range, say 0 to 10⁴?
When the value range is limited, you can use a fixed‑size boolean array (bucket) of size 10⁴ + 1 for presence tracking, yielding O(n) time and O(k) space where k is the range size, which is effectively O(1) extra space relative to n.
Q3Explain how you would adapt the duplicate detection to work on a distributed stream of numbers across multiple machines.
Partition the stream by a hash of the value so that identical numbers land on the same node, then each node runs a local duplicate check using a hash set; a global duplicate exists if any node reports a collision, which can be coordinated via a lightweight aggregator or gossip protocol.
Examples
Input
[2, 5, 1, 2, 3, 5]
Output
true
Explanation: Scanning the array, the value `2` appears at indices 0 and 3, and the value `5` appears at indices 1 and 5. Since a duplicate exists, the result is true.
Input
[10, -3, 7, 4, 9]
Output
false
Explanation: All five numbers are distinct; no value repeats. Consequently, the function returns false.
Input
[0, 0]
Output
true
Explanation: The two elements are identical (`0`), so a duplicate is present and the answer is true.
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- Expected time complexity: O(n)
- Expected auxiliary space: O(n) (e.g., a hash set)
Optimal Approach & Strategy
Create an empty hash set and iterate through the array once, checking if each element is already in the set. If it is, return true; otherwise, insert it. This yields O(n) time with O(n) additional space.
Brute Force Approach
Compare every element with every other element using two nested loops. This checks all possible pairs but runs in O(n²) time, which is too slow for large inputs.
Verified Code Solutions
function containsDuplicate(nums) {
let numSet = new Set();
for (let num of nums) {
if (numSet.has(num)) {
return true;
}
numSet.add(num);
}
return false;
}class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> numSet;
for (int num : nums) {
if (numSet.find(num) != numSet.end()) {
return true;
}
numSet.insert(num);
}
return false;
}
};import java.util.HashSet;
import java.util.Set;
public class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
if (!numSet.add(num)) {
return true;
}
}
return false;
}
}def containsDuplicate(nums):
num_set = set()
for num in nums:
if num in num_set:
return True
num_set.add(num)
return Falsefunction containsDuplicate(nums) {
let numSet = new Set();
for (let num of nums) {
if (numSet.has(num)) {
return true;
}
numSet.add(num);
}
return false;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.