Contains Duplicate solution and explanation
TCS
Google
IBM
Infosys
9 more videos on this problem
Contains Duplicate - Leetcode 217 - PythonNeetCode · 6:31 · 1M views
LeetCode Contains Duplicate Solution Explained - JavaNick White · 5:28 · 109K views
Contains Duplicate (LeetCode 217) | Full solution with HashSet explanation | Study AlgorithmsNikhil Lohia · 10:41 · 39K views
Contains Duplicate - Leetcode 217 - Hashmaps & Sets (Python)Greg Hogg · 1:51 · 20K views
Contains Duplicate - LeetCode 217 - JavaScriptAlgoJS · 1:39 · 4K views
Leetcode | 217. Contains Duplicate | Easy | Java SolutionDeveloper Docs · 3:08 · 4K views
Contains Duplicate - LeetCode 217 - PythonDeepti Talesra · 9:11 · 2K views
Contains Duplicate | LeetCode 217 | Theory + Python codeSai Anish Malla · 6:03 · 1K views
Contains Duplicate | LeetCode 217 | JavaTech Tutor · 4:55 · 1K views
217. Contains Duplicate LeetCode Javascript SolutionJSDev · 4:52 · 706 views
The problem
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.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109
Approach overview
Problem Overview: You receive an integer array nums. The task is to determine whether any value appears at least twice. If a duplicate exists, return true; otherwise return false. The challenge is detecting repeated values efficiently without unnecessary comparisons.
Approach 1: HashSet Lookup (O(n) time, O(n) space)
The most practical solution uses a hash-based set to track elements you have already seen. Iterate through the array once. For each value, check whether it already exists in the set. A hash lookup is O(1) on average, so detecting a duplicate becomes an immediate constant-time check. If the value exists, return true. Otherwise insert it into the set and continue scanning the array.
The key insight is that a set guarantees uniqueness. Instead of comparing each number with every other number, the algorithm converts the duplicate detection problem into repeated hash lookups. This approach scales well for large arrays and works regardless of input ordering. Problems involving fast membership checks frequently rely on a hash table or set structure, especially when working with an array.
Approach 2: Sorting the Array (O(n log n) time, O(1) or O(log n) space)
Another option is to sort the array first, then scan for adjacent equal elements. After sorting, any duplicates must appear next to each other. Iterate from index 1 to n-1 and compare each element with the previous one. If nums[i] == nums[i-1], a duplicate exists.
The cost comes from the sorting step, which typically runs in O(n log n) time. Space usage depends on the sorting algorithm. In-place sorts like heapsort use constant space, while implementations such as Timsort may use O(log n) stack space. This method works well when the array is already being sorted for another operation or when minimizing extra memory is important. Many duplicate-detection tasks can be solved this way using techniques from sorting.
Recommended for interviews: Interviewers generally expect the HashSet solution. It demonstrates awareness of hash-based data structures and achieves optimal O(n) time. The sorting approach shows algorithmic flexibility and awareness of memory tradeoffs, but it is usually considered a secondary option since it increases time complexity. Showing both approaches signals strong problem-solving instincts: brute reasoning first, then the optimal hash-based strategy.
Approach 1: Using a HashSet to Check for Duplicates
This approach leverages the properties of a HashSet (or similar data structures depending on the programming language), which allows for average O(1) time complexity for insertion and lookup operations. As you iterate over the array, you check if the current element is already in the HashSet. If it is, then a duplicate has been found, and you can return true immediately. If it’s not already in the HashSet, you add it. If no duplicates are found by the end of the array, you return false.
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return Falseimport java.util.HashSet;
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;
}#include <vector>
#include <unordered_set>
bool containsDuplicate(std::vector<int>& nums) {
std::unordered_set<int> seen;
for (int num : nums) {
if (seen.find(num) != seen.end()) {
return true;
}
seen.insert(num);
}
return false;
}function containsDuplicate(nums) {
let seen = new Set();
for (let num of nums) {
if (seen.has(num)) {
return true;
}
seen.add(num);
}
return false;
}#include <stdbool.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
bool containsDuplicate(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
for (int i = 0; i < numsSize - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}using System.Collections.Generic;
public class Solution {
public bool ContainsDuplicate(int[] nums) {
HashSet<int> seen = new HashSet<int>();
foreach (int num in nums) {
if (seen.Contains(num)) {
return true;
}
seen.Add(num);
}
return false;
}
}The Python solution also uses a set to efficiently check for duplicates. As we iterate, each element is checked against the set and added to it if it's not already present.
Time Complexity: O(n).
Space Complexity: O(n), for storing elements in the set.
Approach 2: Sorting Approach
This approach involves sorting the array first, then checking for duplicates by comparing each element with its next neighbor. If duplicates exist, they will appear next to each other after sorting.
def containsDuplicate(nums):
nums.sort()
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
return True
return Falseimport java.util.Arrays;
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}#include <vector>
#include <algorithm>
bool containsDuplicate(std::vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}function containsDuplicate(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;
}#include <stdbool.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
bool containsDuplicate(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
for (int i = 0; i < numsSize - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}using System;
public class Solution {
public bool ContainsDuplicate(int[] nums) {
Array.Sort(nums);
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
}Python's built-in sort is applied to the list, allowing for a post-sort scan to quickly identify consecutive duplicates.
Time Complexity: O(n log n).
Space Complexity: O(1), considering sorting modifies the list in place.
Approach 3: Sorting
First, we sort the array nums.
Then, we traverse the array. If there are two adjacent elements that are the same, it means that there are duplicate elements in the array, and we directly return true.
Otherwise, when the traversal ends, we return false.
The time complexity is O(n times log n), where n is the length of the array nums.
function containsDuplicate(nums: number[]): boolean {
nums.sort((a, b) => a - b);
const n = nums.length;
for (let i = 1; i < n; i++) {
if (nums[i - 1] === nums[i]) {
return true;
}
}
return false;
}func containsDuplicate(nums []int) bool {
sort.Ints(nums)
for i, v := range nums[1:] {
if v == nums[i] {
return true
}
}
return false
}impl Solution {
pub fn contains_duplicate(mut nums: Vec<i32>) -> bool {
nums.sort();
let n = nums.len();
for i in 1..n {
if nums[i - 1] == nums[i] {
return true;
}
}
false
}
}class Solution {
/**
* @param Integer[] $nums
* @return Boolean
*/
function containsDuplicate($nums) {
$numsUnique = array_unique($nums);
return count($nums) != count($numsUnique);
}
}Approach 4: Hash Table
We traverse the array and record the elements that have appeared in the hash table s. If an element appears for the second time, it means that there are duplicate elements in the array, and we directly return true.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
function containsDuplicate(nums: number[]): boolean {
return new Set<number>(nums).size !== nums.length;
}func containsDuplicate(nums []int) bool {
s := map[int]bool{}
for _, v := range nums {
if s[v] {
return true
}
s[v] = true
}
return false
}use std::collections::HashSet;
impl Solution {
pub fn contains_duplicate(nums: Vec<i32>) -> bool {
nums.iter().collect::<HashSet<&i32>>().len() != nums.len()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a HashSet to Check for Duplicates | Time Complexity: O(n). |
| Sorting Approach | Time Complexity: O(n log n). |
| Sorting | – |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Lookup | O(n) | O(n) | General case; fastest solution with constant-time duplicate checks |
| Sorting + Adjacent Comparison | O(n log n) | O(1) to O(log n) | Useful when memory is limited or when the array must be sorted anyway |
Frequently asked questions
Is Contains Duplicate easy or hard?
Contains Duplicate is classified as an Easy problem. The main concept is recognizing that a hash set can replace nested loops, reducing the naive O(n^2) duplicate check to an O(n) linear scan.
Contains Duplicate Python/Java solution
Python solutions typically use the built-in set type for O(1) lookups, while Java implementations use HashSet. Both follow the same idea: iterate through the array, check if the element already exists in the set, and return true if a duplicate is found.
How to solve Contains Duplicate in O(n)?
Use a HashSet to track numbers you have already seen. Traverse the array once, checking whether each value exists in the set. If it does, return true immediately; otherwise insert the value into the set. The single pass plus constant-time lookups produces O(n) time complexity.
What is the best approach for Contains Duplicate?
The HashSet approach is the most efficient and commonly expected solution. Iterate through the array and store each number in a set. If a number already exists in the set, a duplicate is found. This method runs in O(n) time with O(n) extra space.
Is Contains Duplicate asked at Google/Amazon/Meta?
Contains Duplicate is a common warm-up problem used in interview screens at companies like Amazon, Meta, and Google. It tests understanding of hash tables, time complexity optimization, and the ability to replace nested comparisons with constant-time lookups.
What data structure is used in Contains Duplicate?
The most common data structure is a HashSet (or hash table). It provides average O(1) insertion and membership checks, which allows fast detection of repeated elements while scanning the array once.
What is the time complexity of Contains Duplicate?
The optimal solution runs in O(n) time using a hash set because each insertion and lookup averages constant time. A sorting-based approach takes O(n log n) time due to the sorting step, followed by a linear scan to detect adjacent duplicates.