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.
1function findDuplicates(nums) {
2 let duplicates = [];
3 nums.forEach(num => {
4 let index = Math.abs(num) - 1;
5 if (nums[index] < 0) {
6 duplicates.push(Math.abs(num));
7 } else {
8 nums[index] = -nums[index];
9 }
10 });
11 return duplicates;
12}JavaScript utilizes the forEach function to iterate and manipulate the nums array using absolute values to detect and store duplicates.
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.
JavaScript uses two interventions: initial reorder loop and subsequent comparison loop for duplicates by ensuring each value aligns with its index.