Watch 10 video solutions for Find All Duplicates in an Array, a medium level problem involving Array, Hash Table. This walkthrough by Nick White has 154,765 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= nnums appears once or twice.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 | 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) |