Contains Duplicate
What is this problem about?
The Contains Duplicate interview question is a fundamental task: given an integer array, return true if any value appears at least twice, and return false if every element is distinct. It is often the first problem a candidate encounters in a technical screen.
Why is this asked in interviews?
Companies like Microsoft and Amazon use the Contains Duplicate coding problem to assess basic coding hygiene and knowledge of space-time trade-offs. It's a "level-setting" question that determines if a candidate knows when to use a Hash Table for O(1) lookups versus Sorting for O(1) extra space.
Algorithmic pattern used
This problem follows the Array, Hash Table, Sorting interview pattern.
- Hash Set approach (O(N) time, O(N) space): Iterate through the array and store each element in a Set. If an element is already in the set, a duplicate is found.
- Sorting approach (O(N log N) time, O(1) space): Sort the array and check if any two adjacent elements are identical.
Example explanation
Input: [1, 2, 3, 1]
- Hash Set: {}
- Process 1: Add 1. Set: {1}
- Process 2: Add 2. Set: {1, 2}
- Process 3: Add 3. Set: {1, 2, 3}
- Process 1: 1 is already in Set! Return true.
Common mistakes candidates make
- Using nested loops: Implementing an O(N^2) solution, which is inefficient.
- Not knowing the return early rule: Continuing to iterate after finding the first duplicate.
- Language-specific efficiency: Not using the built-in Set implementation of their language.
Interview preparation tip
Always discuss the trade-offs. If the interviewer asks for O(1) extra space, you must sort. If they ask for the fastest time, use a Hash Set.
