Find All Duplicates in an Array - Solution & Explanation
Problem Statement
Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most twice, return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, excluding the space needed to store the output
Example 1:
Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]
Example 2:
Input: nums = [1,1,2] Output: [1]
Example 3:
Input: nums = [1] Output: []
Constraints:
n == nums.length1 <= n <= 1051 <= nums[i] <= n- Each element in
numsappears once or twice.
Approach Overview
Problem Overview: Given an integer array where 1 ≤ nums[i] ≤ n and n = nums.length, some values appear twice while others appear once. Return all elements that appear exactly twice. The constraint that values map directly to array indices allows clever in-place tricks using the array itself as a bookkeeping structure.
Approach 1: Negation Marking (O(n) time, O(1) space)
This technique treats the array as a presence map. Iterate through the array and use the absolute value of each number as an index. When visiting value x, check position x-1. If the number at that index is positive, negate it to mark that x has been seen. If it's already negative, the value x has appeared before, so it is a duplicate. This works because each number falls within the range 1..n, guaranteeing a valid index. The algorithm performs a single pass and modifies the array in-place, making it both time-efficient and memory-efficient compared to using a hash table.
Approach 2: Index-Based Value Reordering (O(n) time, O(1) space)
This method reorders numbers so each value ideally sits at its correct index (value - 1). Iterate through the array and repeatedly swap elements until the current value is either already in the correct position or a duplicate blocks the placement. If you encounter a value x where nums[x-1] already equals x, then x must be duplicated. The technique resembles cyclic placement and ensures each number moves at most once or twice, keeping the total runtime linear. This approach is useful when you prefer explicit index positioning rather than sign manipulation.
Recommended for interviews: Negation marking is typically the expected optimal solution. It demonstrates awareness of how to exploit the 1..n constraint and use the array as an in-place visited structure. Index-based reordering also achieves O(n) time and O(1) space, but involves more swaps and edge-case handling. Interviewers usually expect candidates to first recognize that a brute-force or hash map approach would require O(n) extra space, then optimize by converting the array itself into the tracking structure.
Approach 1: Negation Marking
Negation Marking: This approach leverages the integer constraints (1 to n) to use the input array itself to track occurrences. Every time an index is visited based on an element's value, we negate the number at that index if it's positive. If we encounter that index again and the number is already negative, it means the number corresponding to this index has been seen before.
This Python solution iterates through the list, converting the number at the index derived from each element into its negative. If an index points to an already negative number, it indicates the presence of a duplicate, and hence, the number is added to the duplicates list.
Complexity
Time Complexity: O(n) as it traverses the list once.
Space Complexity: O(1) as it uses no additional space apart from the output list.
Approach 2: Index-Based Value Reordering
Index-Based Value Reordering: In this approach, we aim to place each number at the position corresponding to its value. If a position already holds the correct number, it signifies a duplicate, since we're attempting to place a number in its designated index. This allows us to directly identify duplicates while keeping the array order in check.
This Python solution places each number at its correct index (e.g., 1 at index 0). If a correct position is already occupied by the number, a duplicate is detected.
Complexity
Time Complexity: O(n) due to swapping.
Space Complexity: O(1) as no extra space except for output.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Negation Marking | Time Complexity: O(n) as it traverses the list once. |
| Index-Based Value Reordering | Time Complexity: O(n) due to swapping. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Negation Marking | O(n) | O(1) | Best general solution when array values are in range 1..n and modification of the array is allowed |
| Index-Based Value Reordering | O(n) | O(1) | Useful when you prefer placing elements at their correct indices (cyclic placement style problems) |
Video Solution
LeetCode 442. Find All Duplicates in an Array (Solution Explained) • Nick White • 154,872 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find All Duplicates in an Array easy or hard?
Find All Duplicates in an Array Python/Java solution
How to solve Find All Duplicates in an Array in O(n)?
What is the best approach for Find All Duplicates in an Array?
Is Find All Duplicates in an Array asked at Google/Amazon/Meta?
What data structure is used in Find All Duplicates in an Array?
What is the time complexity of Find All Duplicates in an Array?
Ready to solve this problem?
Practice Find All Duplicates in an Array with our built-in code editor and test cases.
Practice on FleetCode