⚡Flashcard Drill➔
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

  1. Because values lie in [1, n], the value itself indexes a slot: v maps to v - 1.
  2. For each element, take abs(x) to recover the original value (the slot may already be negated), then inspect nums[abs(x) - 1].
  3. 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.
  4. The abs call 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 subsequent abs(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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems