Given an integer array nums of length n where all the integers are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appear twice. You must write an algorithm that runs in O(n) time and uses only constant extra space.
Java
Find All Duplicates in an Array
Given an integer array nums of length n where all the integers are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appear twice. You must write an algorithm that runs in O(n) time and uses only constant extra space.
Example 1:
Input: [4,3,2,7,8,2,3,1]
Output: [2,3]
Input
arr =[4,3,2,7,8,2,3,1]
Find all elements that appear twice. Values are in range [1, 8]
Current
Checking Index
Negative (Seen)
Duplicate Found
Array (values 1 to n, using index = |value| - 1 to mark seen)
4
[0]
3
[1]
2
[2]
7
[3]
8
[4]
2
[5]
3
[6]
1
[7]
Algorithm: For each value v, check index |v| - 1
- If nums[|v| - 1] is positive: negate it (mark as seen)
- If nums[|v| - 1] is already negative: v is a duplicate!