442. Find All Duplicates in an Array
Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 69.1%
Problem Breakdown
We are given an array of integers where every element satisfies , and is the length of the array. Some elements appear twice, others once. We need to return all values that appear exactly twice (or more than once? The problem says “appear twice”, but typically in this LeetCode variant we look for any duplicates).
Inputs: An integer list nums.
Outputs: A list containing integers appearing at least twice.
Constraints:
- Time Complexity: Must be . We cannot afford nested loops or sorting ( is often acceptable, but the prompt specifically asks for O(n)).
- Space Complexity: Must be extra space (excluding output). This rules out using a Hash Set to track seen numbers.
Edge Cases/Implicit Constraints:
- Values are strictly positive and bounded by array size (), which is the key constraint enabling an in-place solution.
- Empty input: The loop won’t execute, returning an empty list correctly.
- Overflow: Python handles large integers automatically; logic relies on indices fitting within bounds .
Intuition
A brute-force approach would be to use a Hash Set or frequency map to track seen numbers as we iterate through the array. However, this requires extra space for the set/map, violating our constraints. Sorting takes time and potentially modifies order (though not strictly forbidden by “no extra space” if done in-place sort like Heapsort/Quicksort, but it’s slower).
The key insight lies in the constraint: .
This means every number present can be mapped directly to an index within the array itself (specifically index = value - 1). We don’t need external storage; we can use the input array as our own hash map.
We can treat each element’s sign at its corresponding index (value - 1) as a flag:
- If
nums[index]is positive, it means we haven’t seen this number before (or rather, that slot hasn’t been marked). - If
nums[index]is negative, it means the value associated with that index has already appeared.
By iterating through each element and flipping the sign of the corresponding target index, we can detect duplicates in a single pass without allocating new memory.
Approach
- Initialize an empty list to store results (duplicates).
- Iterate through every number
xin the array using its current position as our cursor. - For each element
nums[i], take its absolute value (abs(nums[i])) because previous operations might have negated this slot’s sign when we marked it for a different pointer. This gives us the original “value” to use as an index. - Calculate the target index:
target_index = abs(nums[i]) - 1. - Check if
nums[target_index]is negative.- If yes, we have encountered this value before (it points here). Add it to our results list and continue.
- If no, negate the number at that index (
nums[target_index] *= -1) to mark it as visited for future checks.
- Return the collected duplicates.
Complexity Analysis
- Time: . We iterate through the array exactly once. Inside the loop, operations (absolute value check, sign flip, list append) are constant time .
- Space: auxiliary space. We modify the input array in-place to store state information and only use a few variables for iteration. The output list is not counted towards extra space complexity per standard LeetCode definitions (though technically proportional to number of duplicates).
Solution
def findDuplicates(nums):
"""
Finds all elements that appear twice using O(1) space and O(n) time.
Args:
nums (List[int]): Array where 1 <= a[i] <= n
Returns:
List[int]: Elements appearing more than once
"""
duplicates = []
for i in range(len(nums)):
# Get the absolute value to handle previously negated indices.
val = abs(nums[i]) - 1
# If nums[val] is negative, we've seen this number before (duplicate).
if nums[val] < 0:
duplicates.append(val + 1)
# Mark index 'val' as visited by negating the value there.
else:
nums[val] *= -1
return duplicates
Edge Cases Handled
- Empty Array: The loop range is empty, function returns
[]. Correct behavior for no elements to check. - No Duplicates: Every index visited will be positive when checked; nothing added to list. Returns
[]. - All Elements Same (e.g.,
[2, 2]): First pass marks index 1 negative. Second pass sees it is negative and adds value to duplicates. Correctly identifies the duplicate count logic for “appearing twice”. - Values at Boundaries: Values map to index
0, values map to indexn-1. Python list bounds are respected by problem constraints ().