Find All Duplicates in an Array
Given an array of integers, where $1 \leq a[i] \leq n$, some elements appear twice and others appear once. Find all the elements that appear twice. Solve without extra space and in $O(n)$ runtime.
Why Interviewers Ask This
Meta interviewers ask this to evaluate your mastery of in-place array manipulation and index-based hashing. They specifically test if you can optimize space complexity to O(1) while maintaining linear time, a common requirement for high-scale systems where memory is constrained. This problem reveals whether you understand how to repurpose existing data structures creatively rather than relying on standard library helpers.
How to Answer This Question
To answer this effectively, follow a structured four-step framework: Clarify, Analyze, Design, and Verify. First, clarify constraints like input mutability and edge cases such as empty arrays or negative numbers. Second, analyze the mathematical property that values map directly to indices since elements are between 1 and n. Third, design an in-place marking strategy using negation; iterate through the array, treat each value as an index, and flip the sign of the element at that index. If the target index is already negative, you found a duplicate. Finally, verify your solution by tracing it with a concrete example like [4,3,2,7,8,2,3,1] to ensure no extra space is used and runtime remains O(n).
Key Points to Cover
- Explicitly mention the constraint mapping values to indices (1 to n)
- Demonstrate the in-place negation technique clearly
- Explain why O(1) space is achieved without auxiliary data structures
- Confirm the algorithm handles duplicates correctly without false positives
- Discuss potential side effects of modifying the input array
Sample Answer
I would start by acknowledging the constraints: we need O(n) time and O(1) extra space. Since the input contains integers from 1 to n, I can use the array indices themselves as a hash map. My approach involves iterating through the array once. For each number 'x', I calculate its corresponding index as 'abs(x) - 1'. I then check the value at that index. If the value is positive, I negate it to mark that the number 'x' has been seen. If the value is already negative, it means we have encountered 'x' before, so I add 'x' to my results list.
For example, with input [4,3,2,7,8,2,3,1], when I process the first 4, I negate the element at index 3 (value 7 becomes -7). Later, when I encounter 7 again, I see the element at index 6 is already negative, confirming 7 is a duplicate. This method modifies the input array but strictly adheres to the O(1) space requirement. It runs in a single pass, ensuring O(n) time complexity. This technique is particularly relevant for Meta's engineering culture, which values efficient resource utilization in large-scale distributed systems.
Common Mistakes to Avoid
- Using a HashSet or frequency map, which violates the O(1) space constraint
- Sorting the array first, which increases time complexity to O(n log n)
- Failing to handle the absolute value when accessing indices after negation
- Not clarifying if modifying the original input array is permitted
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.