Skip to main content
Talentd

Contains Duplicate - Solution & Explanation

EasyArrayHash TableSorting17 min readAsked at: Amazon, Microsoft, Apple +17
Practice this problem

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.

 

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.

In the C solution, we sort the array using qsort() and then check each adjacent pair of elements for duplication. This is efficient given the constraints, as sorting the array is O(n log n) and the subsequent scan is O(n).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(1), no extra space required apart from sorting.

Try this approach in the editor →

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.

Here, qsort is used to sort the array, which allows for efficient comparison of adjacent elements to find duplicates. This leverages sorting's ability to bring identical elements together.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1), aside from sorting in-place.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHPC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

C

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using a HashSet to Check for Duplicates

Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(1), no extra space required apart from sorting.

Sorting Approach

Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1), aside from sorting in-place.

Sorting—
Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashSet LookupO(n)O(n)General case; fastest solution with constant-time duplicate checks
Sorting + Adjacent ComparisonO(n log n)O(1) to O(log n)Useful when memory is limited or when the array must be sorted anyway

Video Solution

Contains Duplicate - Leetcode 217 - Python • NeetCode • 1,080,792 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Contains Duplicate with our built-in code editor and test cases.

Practice on FleetCode
Previous

Contains Duplicate II

Next

Contains Duplicate III