Contains Duplicate
Asked at Google, Netflix
Problem
Given an integer array, return true if any value appears at least twice, and false if every element is distinct. This is the simplest version of the duplicate detection pattern and serves as a warm-up for its harder variants.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Netflix | Easy | View all Netflix questions → |
How to Think About It
Brute force: compare every pair of elements. Two nested loops, O(n^2) time. Works but way too slow.
Better: sort the array first, then scan for adjacent duplicates. O(n log n) time, O(1) space (if sorting in-place). The O(n log n) sort dominates.
Optimal: use a hash set. For each element, check if it's already in the set. If yes, return true. If no, add it. O(n) time, O(n) space. The set guarantees uniqueness.
Why hash set over hash map: you only need to know IF an element exists, not WHERE it is. A set is simpler and uses less memory per element.
Visual walkthrough for [1,2,3,1]:
Set: {}
1: not in set. Set: {1}
2: not in set. Set: {1,2}
3: not in set. Set: {1,2,3}
1: in set! Return true.
Edge cases: empty array (return false), single element (return false), all same (return true).
Optimal Approach
Use a hash set. For each element:
- If element is in set, return true (duplicate found).
- Add element to set.
- After the loop, return false (no duplicates).
Time: O(n) -- one pass. Space: O(n) for the hash set.
What Trips People Up in Real Interviews
Sorting first and comparing adjacent elements. That's O(n log n). The hash set approach is O(n). The interviewer may ask you to solve it without extra space -- then sorting is the answer.
Confusing "at least twice" with "exactly twice." The problem asks if ANY value appears at least twice. One duplicate is enough to return true.
Not handling edge cases: empty array (return false), single element (return false). These seem trivial but are easy to forget under pressure.
Using a hash map instead of a hash set. A map stores key-value pairs, wasting memory. A set stores just the keys.
Trying to solve it without any data structure. Without a set or sorting, you need O(n^2) brute force. There's no O(n) time, O(1) space solution for this problem.
Solution Code
def containsDuplicate(nums):
return len(nums) != len(set(nums))Frequently Asked Questions
What is the Contains Duplicate problem?
Given an integer array, return true if any value appears at least twice, and false if every element is distinct. This is the simplest version of the duplicate detection pattern and serves as a warm-up for its harder variants.
How do you solve Contains Duplicate?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Contains Duplicate?
Contains Duplicate is asked at Google, Netflix. It is a easy difficulty problem.
What are common mistakes on Contains Duplicate?
- Sorting first and comparing adjacent elements. That's `O(n log n)`. The `hash set` approach is `O(n)`. The interviewer may ask you to solve it without extra space -- then sorting is the answer.
- Confusing "at least twice" with "exactly twice." The problem asks if ANY value appears at least twice. One duplicate is enough to return true.
- Not handling edge cases: empty array (return false), single element (return false). These seem trivial but are easy to forget under pressure.
- Using a `hash map` instead of a `hash set`. A map stores key-value pairs, wasting memory. A set stores just the keys.
- Trying to solve it without any data structure. Without a set or sorting, you need `O(n^2)` brute force. There's no `O(n)` time, `O(1)` space solution for this problem.