NeetCode #154LC-442MediumArrays & Hashing
← Back to All Problems#154 · #442 · Find All Duplicates in an Array(数组中重复的数据)
📌 Problem Statement & Constraints
Given an integer array
nums of length n where every element is in [1, n] and each element appears once or twice, return all elements that appear twice. Constraints: 1 <= n <= 10^5. Solve it in O(n) time with O(1) auxiliary space.💡 Core Algorithmic Approaches
- Because values lie in
[1, n], the value itself indexes a slot:vmaps tov - 1. - For each element, take
abs(x)to recover the original value (the slot may already be negated), then inspectnums[abs(x) - 1]. - If that slot is already negative, the value has been seen before, so it is a duplicate. Otherwise negate it to mark the value as seen.
- The
abscall is essential -- without it, a previously negated slot yields a negative index, and Python would silently wrap around to the end of the list.
💻 Benchmark Python3 Implementation
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
res = []
for x in nums:
idx = abs(x) - 1 # abs is required: the slot may be negated
if nums[idx] < 0:
res.append(abs(x)) # second sighting
else:
nums[idx] = -nums[idx] # mark as seen
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1) auxiliary (the output is excluded), since the input array serves as the marking structure.
⚠️ Interview Pitfalls & Follow-ups
- Omitting
abs: a negated slot produces a negative index, which Python interprets as counting from the end, silently corrupting the result. - Using a set: O(n) space, violating the O(1) requirement.
- Marking with
nums[idx] = 0: this works for duplicates but destroys the value, so subsequentabs(x)calls return 0 and the marking breaks. - Assuming values can exceed n: the constraints guarantee
nums[i] <= n, which is what makes value-as-index valid.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.