Learning Outcome
After this lesson, you should be able to count values and add a duplicate to the answer only when its frequency reaches 2.
Problem Statement
Given an array, return all values that appear at least twice.
| Input | Output | Why |
|---|---|---|
nums = [4,3,2,7,8,2,3,1] | [2,3] | The values 2 and 3 appear more than once. |
Brute Force Approach
For each element, scan the rest of the array to check whether it appears again. This is quadratic.
Optimized Approach
Use a frequency map. Increment the count for each value and append the value exactly when its count becomes 2.
Exact Pseudocode
freq = empty map
answer = []
for x in nums:
freq[x] += 1
if freq[x] == 2:
answer.add(x)
return answerReference Code
class Solution:
def findDuplicates(self, nums):
freq = {}
answer = []
for x in nums:
freq[x] = freq.get(x, 0) + 1
if freq[x] == 2:
answer.append(x)
return answerSample Dry Run
| Step | State | Result |
|---|---|---|
| 4,3,2,7,8 | All counts become 1 | answer = [] |
| Second 2 | count becomes 2 | answer = [2] |
| Second 3 | count becomes 2 | answer = [2,3] |
| Finish | 1 has count 1 | return [2,3] |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | Each number updates one hashmap entry. |
| Space | O(n) | The map can store every distinct number. |
Edge Cases
- A value appearing three times should still be returned once.
- An array with no duplicates returns an empty list.
- Negative values work with a hashmap.
Interview Checklist
- Append only when count becomes exactly 2.
- Use a map if values are not limited to a small range.
- Do not append again when count becomes 3 or more.
FAQs
Why append when count is 2?
That is the first moment we know the value is duplicated, and it prevents duplicate output entries.
Can this be done in-place?
Some constrained versions allow index marking, but the hashmap version is clearer and works for general values.
What is the core pattern?
Frequency counting.