Contains Duplicate
An easy Arrays problem included in Apna College, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Arrays
- Sheets
- 2
- Core for
- 25 roles
- Platform
- LeetCode
The problem
Given an integer array, determine whether any element appears at least twice in the collection.
Example 1
- Input
- nums = [1,2,3,1]
- Output
- true
- Why
- The value 1 appears at index 0 and index 3, satisfying the duplicate condition.
Example 2
- Input
- nums = [1,2,3,4]
- Output
- false
- Why
- Every value in the array is distinct, so no duplicates exist.
Example 3
- Input
- nums = [1,1,1,3,3,4,3,2,4,2]
- Output
- true
- Why
- Multiple elements including 1, 2, 3, and 4 appear more than once.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
How to think about it
Updated 2026-09-09The question does not care where copies sit or how many times a duplicate repeats; it only asks if the count of unique values is strictly less than the total count. Tracking seen keys in an unordered hash set detects collisions the moment a repeated number is encountered, short-circuiting the remainder of the array.
Approaches, worst first
Nested pair comparison
time O(n^2) · space O(1)
Compare every pair of elements using nested loops to verify if nums[i] == nums[j]. Requires no auxiliary memory, but runs in quadratic time and times out on larger arrays.
Sort and adjacent check
time O(n log n) · space O(1)
Sort the array ascending so duplicate values cluster into adjacent positions. A single linear scan checks whether nums[i] == nums[i - 1]. Avoids dynamic memory allocation at the cost of an O(n log n) sorting step and mutating the input order.
Hash set membership testWrite this one
time O(n) · space O(n)
Traverse elements while adding each to a hash set. If an insertion query indicates the value is already present in the set, terminate early and return true. Returns false if the scan finishes with all unique elements.
Where people lose marks · 3
- Allocating a fixed-size boolean frequency array indexed by values when nums[i] contains negative numbers or ranges up to 10^9.
- Comparing the size of the set only after inserting all elements instead of early-exiting on the first duplicate encounter.
- Assuming a single-element array has duplicates instead of returning false immediately.
Full solution
Hash set membership test: one pass, early-exit on the first repeat. The nested-loop and sort-based approaches both work but are strictly worse here — O(n) time and space beats them without the input-mutation tradeoff sorting requires.
Python
def contains_duplicate(nums: list[int]) -> bool:
seen: set[int] = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
JavaScript
function containsDuplicate(nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) return true;
seen.add(num);
}
return false;
}
The theory behind it
Arrays — the ground this problem stands on. All Arrays problems
What Arrays is
An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.
When to reach for it
Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.
How the pattern works
Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.
What each operation costs
| Operation | Time |
|---|---|
| look up element by index | O(1) |
| insert or delete at the start | O(n) |
| search an unsorted collection for a value | O(n) |
What usually goes wrong with Arrays
- Reading past the final index by checking index less than or equal to length instead of strictly less than length, triggering index out of bounds exceptions.
- Modifying length or removing elements during a forward iteration loop, which causes remaining items to shift left and skip validation on the next neighbor.
- Assuming dynamic resizing is costless inside nested loops, causing repeated memory reallocation copies when appending unknown quantities of items.
Which roles need this problem
Arrays is a core topic for these 25 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 3 more roles, including Database Engineer, Bioinformatics Engineer, Networking Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Arrays problems
Problem set and role mapping as of .