How to Solve: Contains Duplicate – Complete Guide for FAANG Interviews

How to Solve: Contains Duplicate – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 FAANG onsite interviews—master it, and you instantly prove you can optimize for time, space, and edge cases under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling "Contains Duplicate," ensure you understand: 1. Hash Sets – O(1) average-time insert/lookup, used for tracking seen elements. 2. Time-Space Tradeoffs – When to use extra space (hash set) vs. sorting (O(1) space but O(n log n) time). 3. Edge Cases – Empty input, single-element input, all duplicates, no duplicates.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Run this every time you see a "Contains Duplicate" variant:

1. Clarify the Problem
2. Are duplicates anywhere in the array, or within a fixed window (e.g., k indices apart)?
3. Is the input sorted? If not, can we sort it?

4. Are we allowed to modify the input (e.g., sorting)?

5. Choose the Right Technique

6. O(n) time, O(n) space? → Hash set.
7. O(1) space? → Sort + linear scan.

8. Follow-up (e.g., "within k range")? → Hash map (track indices).

9. Handle Edge Cases

10. Empty array → Return False.
11. Single element → Return False.

12. All duplicates → Return True immediately.

13. Optimize for Early Termination

14. Exit as soon as a duplicate is found (don’t process the entire array).

15. Write Pseudocode First

16. Sketch the logic before coding (e.g., for num in nums: if num in seen: return True).

17. Code & Test

18. Write the solution, then test with:

    • [1, 2, 3, 1] → True
    • [1, 2, 3, 4] → False
    • [] → False
    • [1, 1, 1, 1] → True

19. Analyze Time & Space Complexity

20. Hash set: O(n) time, O(n) space.
21. Sorting: O(n log n) time, O(1) space.

? WORKED EXAMPLES

Example 1 – Basic: Contains Duplicate (LeetCode 217)

Problem: Given an integer array nums, return True if any value appears at least twice, else False.

Step-by-Step Solution

1. Clarify: Duplicates can be anywhere in the array.
2. Technique: Hash set (O(n) time, O(n) space).
3. Edge Cases: Empty array → False.
4. Pseudocode:
   seen = set()
for num in nums:
if num in seen: return True
seen.add(num)
return False
5. Code (Python):
   python
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
6. Complexity:
7. Time: O(n) (each insertion/lookup is O(1) average).
8. Space: O(n) (worst-case: all elements are unique).

Why This Works: - A hash set provides O(1) lookups, so we can check for duplicates in a single pass.

Example 2 – Medium: Contains Duplicate II (LeetCode 219)

Problem: Given an integer array nums and an integer k, return True if there are two distinct indices i and j such that nums[i] == nums[j] and abs(i - j) <= k.

Step-by-Step Solution

1. Clarify: Duplicates must be within k indices of each other.
2. Technique: Hash map (track last seen index of each number).
3. Edge Cases:
4. k = 0 → Only check if nums[i] == nums[i] (always False unless duplicates exist).
5. Empty array → False.
6. Pseudocode:
   seen = {}
for i, num in enumerate(nums):
if num in seen and i - seen[num] <= k:
return True
seen[num] = i
return False
7. Code (Python):
   python
def containsNearbyDuplicate(nums, k):
seen = {}
for i, num in enumerate(nums):
if num in seen and i - seen[num] <= k:
return True
seen[num] = i
return False
8. Complexity:
9. Time: O(n) (single pass).
10. Space: O(n) (worst-case: all elements are unique).

Why This Works: - By tracking the last index of each number, we can check if the current index is within k of the previous occurrence.

Example 3 – Hard/Follow-up: Contains Duplicate III (LeetCode 220)

Problem: Given an integer array nums and two integers k and t, return True if there are two distinct indices i and j such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.

Step-by-Step Solution

1. Clarify: Need to find close values (<= t) within a window of k indices.
2. Technique: Sliding window + Bucketing (O(n) time, O(k) space).
3. Edge Cases:
4. t = 0 → Same as "Contains Duplicate II."
5. k = 0 → Only check nums[i] == nums[i] (always False unless duplicates exist).
6. Pseudocode:
   bucket = {}
for i, num in enumerate(nums):
bucket_id = num // (t + 1)
if bucket_id in bucket: return True
if bucket_id - 1 in bucket and abs(num - bucket[bucket_id - 1]) <= t: return True
if bucket_id + 1 in bucket and abs(num - bucket[bucket_id + 1]) <= t: return True
bucket[bucket_id] = num
if i >= k: del bucket[nums[i - k] // (t + 1)]
return False
7. Code (Python):
   python
def containsNearbyAlmostDuplicate(nums, k, t):
if t < 0 or k < 0:
return False
bucket = {}
for i, num in enumerate(nums):
bucket_id = num // (t + 1)
if bucket_id in bucket:
return True
if bucket_id - 1 in bucket and abs(num - bucket[bucket_id - 1]) <= t:
return True
if bucket_id + 1 in bucket and abs(num - bucket[bucket_id + 1]) <= t:
return True
bucket[bucket_id] = num
if i >= k:
del bucket[nums[i - k] // (t + 1)]
return False
8. Complexity:
9. Time: O(n) (each element is processed once).
10. Space: O(k) (sliding window of size k).

Why This Works: - Bucketing groups numbers into ranges of size t + 1, allowing us to check adjacent buckets for values within t. - Sliding window ensures we only consider indices within k distance.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. When you see ‘Contains Duplicate,’ ask yourself: 1. Are duplicates anywhere in the array? → Hash set, O(n) time. 2. Are duplicates within k indices? → Hash map tracking last seen index. 3. Are we checking close values (<= t) within k indices? → Bucketing + sliding window.

Always handle edge cases: empty array, single element, all duplicates. Optimize for early termination—exit as soon as you find a match. If they ask for O(1) space, sort first and check adjacent elements. And if they throw a curveball like ‘What if k is larger than n?’, just cap the window at the array size.

You’ve got this. Now go crush that interview." ?