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.
1#include <vector>
2#include <cmath>
3
4std::vector<int> findDuplicates(std::vector<int>& nums) {
5 std::vector<int> duplicates;
6 for (int i = 0; i < nums.size(); ++i) {
7 int index = abs(nums[i]) - 1;
8 if (nums[index] < 0) {
9 duplicates.push_back(abs(nums[i]));
10 } else {
11 nums[index] = -nums[index];
12 }
13 }
14 return duplicates;
15}The C++ code makes use of the standard vector library to store the duplicates. We iterate over the array using index manipulations similar to the Python code.
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.
1This Python solution places each number at its correct index (e.g., 1 at index 0). If a correct position is already occupied by the number, a duplicate is detected.