Algorithm Type
Category: Array Manipulation, In-Place Modification
Time Complexity: O(n) (linear time)
Space Complexity: O(1) (constant extra space, ignoring output list)
Technique Used: Index Mapping & Negation
Explanation
It is commonly used in in-place duplicate detection problems, especially when the input array contains numbers from 1 to n. The algorithm tracks duplicates by marking indices as negative instead of using extra space like a hash set. It leverages the fact that all numbers are between 1 and n to use indices as a way to mark seen numbers.
Iterate through the array and compute an index (n = abs(nums[i]) - 1).
Check if nums[n] is already negative:
If yes, this means the number has appeared before → it's a duplicate.
If no, mark it by negating (nums[n] = -nums[n]).
Continue until all elements are processed.
Return the list of duplicates.
Example With Processing Steps:
Input:
nums = {4, 3, 2, 7, 8, 2, 3, 1}i | nums[i] | n (index) | nums[n] before | nums[n] after | res (duplicates) |
|---|---|---|---|---|---|
0 | 4 | 3 | 7 | -7 | [] |
1 | 3 | 2 | 2 | -2 | [] |
2 | 2 | 1 | 3 | -3 | [] |
3 | 7 | 6 | 3 | -3 | [] |
4 | 8 | 7 | 1 | -1 | [] |
5 | 2 | 1 | -3 | -3 | [2] (duplicate) |
6 | 3 | 2 | -2 | -2 | [2,3] (duplicate) |
7 | 1 | 0 | 4 | -4 | [2,3] |
Output:
Duplicate numbers: 2 3public class Solution {
public IList<int> FindDuplicates(int[] nums) {
var res = new List<int>();
for (int i = 0; i < nums.Length; i++)
{
//Iterate through the array and compute an index.
var n = Math.Abs(nums[i]) - 1;
//Check if nums[n] is already negative
if(nums[n] < 0)
{
//If yes, this means the number has appeared before
res.Add(n + 1);
}
//If no, mark it by negating.
nums[n] = -nums[n];
}
//Return the list of duplicates.
return res;
}
}Comparison with Other Duplicate-Finding Algorithms
Algorithm | Time Complexity | Space Complexity | Modifies Input? | Notes |
HashSet-Based (Brute Force) | O(n) | O(n) | No | Uses extra memory |
Sorting-Based | O(n log n) | O(1) | Yes | Requires sorting first |
Negation (This Algorithm) | O(n) | O(1) | Yes | Efficient in-place approach |
Cyclic Sort | O(n) | O(1) | Yes | Alternative for missing & duplicate numbers |
When to Use This Algorithm?
✔ When extra space is not allowed
✔ When numbers are within 1 to n
✔ When O(n) time complexity is needed
❌ Not suitable if numbers can be negative or out of range
❌ Modifies the input array (restoration might be needed)
This approach is commonly used in LeetCode problems like:
"Find All Duplicates in an Array" (LeetCode 442)
"Find the Duplicate Number" (LeetCode 287, with slight modifications)
