Find All Duplicates in an Array

Given an array nums of n integers where each integer is in the range [1, n], return an array of all the integers that appear more than once in the array, sorted in ascending order.

Sample Input and Expected Output:

Input:

nums = [4, 3, 2, 7, 8, 2, 1, 1]

Output:

Duplicates in the array: [1, 2]

Input:

nums = [3, 3, 2, 4, 6, 2, 5, 1]

Output:

Duplicates in the array: [2, 3]

Solution in C++:

The idea is to use the array itself as a hash table. For each number x in the array, we consider its absolute value abs(x) as the index and negate the value at that index. When we encounter a number y at index abs(y), if the value at that index is already negative, it means that abs(y) has appeared before, so abs(y) is a duplicate. We add abs(y) to the result array. After processing all numbers, we return the result array containing all duplicates.

#include <iostream>
#include <vector>
#include <cmath>

std::vector<int> findDuplicates(std::vector<int>& nums) {
    std::vector<int> result;

    for (int num : nums) {
        int index = std::abs(num) - 1; // Convert num to index (zero-based).
        if (nums[index] < 0) {
            result.push_back(index + 1); // If the value at index is negative, it's a duplicate.
        }
        nums[index] = -nums[index]; // Negate the value at index.
    }

    return result;
}

int main() {
    std::vector<int> nums1 = {4, 3, 2, 7, 8, 2, 1, 1};
    std::vector<int> nums2 = {3, 3, 2, 4, 6, 2, 5, 1};

    std::vector<int> result1 = findDuplicates(nums1);
    std::vector<int> result2 = findDuplicates(nums2);

    std::cout << "Duplicates in the array: [";
    for (int num : result1) {
        std::cout << num << " ";
    }
    std::cout << "]" << std::endl;

    std::cout << "Duplicates in the array: [";
    for (int num : result2) {
        std::cout << num << " ";
    }
    std::cout << "]" << std::endl;

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the solution is O(n), where n is the size of the input vector nums. Each number is processed once in the array.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The algorithm is performed in-place without using any extra data structures, except for the result array, which contains duplicates and its size is at most n/2 in the worst case.