Sponsored
Sponsored
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.
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.
1def find_duplicates(nums):
2 duplicates = []
3 for num in nums:
4 index = abs(num) - 1
5 if nums[index] < 0:
6 duplicates.append(abs(num))
7 else:
8 nums[index] = -nums[index]
9 return duplicatesThis 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.
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.
Time Complexity: O(n) due to swapping.
Space Complexity: O(1) as no extra space except for output.
1using System.Collections.Generic;
public class Solution {
public IList<int> FindDuplicates(int[] nums) {
List<int> duplicates = new List<int>();
for (int i = 0; i < nums.Length; i++) {
while (nums[i] != nums[nums[i] - 1]) {
int temp = nums[i];
nums[i] = nums[nums[i] - 1];
nums[temp - 1] = temp;
}
}
for (int i = 0; i < nums.Length; i++) {
if (nums[i] != i + 1) {
duplicates.Add(nums[i]);
}
}
return duplicates;
}
}C# uses list and swaps within the input array to enforce correct ordering, detecting duplicates via out-of-place elements in second pass.