Find All Duplicates in Array
Given an array of integers, find all duplicates in the array. A duplicate is an element that appears more than once in the array.
Constraints:
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
Examples:
Input: [4,3,2,7,8,2,3,1]
Output: [2,3]
Explanation: The elements 2 and 3 appear more than once in the array.
Solutions
Negative Marking
Time: O(n)Space: O(1)
This solution uses the negative marking approach. It iterates through the array and for each element, it calculates its corresponding index. If the element at the calculated index is negative, it means that the current element is a duplicate, so it is added to the result list. Then, the element at the calculated index is negated to mark it as visited.
public int[] findDuplicates(int[] nums) {
List<Integer> duplicates = new ArrayList<>();
for (int i = 0;
i < nums.length;
i++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index] < 0) {
duplicates.add(Math.abs(nums[i]));
}
nums[index] = -nums[index];
}
int[] result = new int[duplicates.size()];
for (int i = 0;
i < duplicates.size();
i++) {
result[i] = duplicates.get(i);
}
return result;
}Follow-up:
Find all duplicates in an array without using extra space.
