Solution Explanation:

This problem asks to find all duplicate numbers in an array where each number appears at most twice and is within the range [1, n], where n is the length of the array. The solution presented uses an in-place approach with O(n) time complexity and O(1) space complexity (excluding output).

Approach:

The core idea is to utilize the array itself as a hash table. We iterate through the array. For each element nums[i], we check if it's in its correct position (i.e., if nums[i] == i + 1). If not, we swap nums[i] with nums[nums[i] - 1]. This process continues until the element is in its correct sorted position. Once the array is mostly sorted, elements that are out of place are the duplicates.

Time Complexity: O(n)

Although there are nested loops, the inner loop for swapping executes at most n times in total across all iterations. Each element is involved in at most one swap. This leads to a linear time complexity.

Space Complexity: O(1)

The algorithm modifies the input array in-place. We use only a constant amount of extra space, excluding the space for storing the result.

Code Explanation (Python):

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            while nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        return [v for i, v in enumerate(nums) if v != i + 1]

1. Iteration: The outer loop iterates through each element of the nums array.

2. Cyclic Sort (inner while loop): The inner while loop performs a cyclic sort. It continues swapping elements until nums[i] is in its correct position (i.e., nums[i] == i + 1). The swapping is done using Python's simultaneous assignment for efficiency. Crucially, this ensures that each number eventually ends up in the correct index (accounting for duplicates).

3. Duplicate Identification: After the cyclic sort, the elements that are not in their correct position are the duplicates. A list comprehension is used to efficiently identify and collect these duplicates.

Code Explanation (Java):

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                ans.add(nums[i]);
            }
        }
        return ans;
    }
 
    void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

The Java code follows the same logic as the Python code. The swap function is explicitly defined for clarity. The final loop collects the duplicate numbers (those out of their sorted position) into an ArrayList.

The C++, Go, and other language solutions implement the same algorithm with syntax changes specific to each language. The core principle of cyclic sort remains consistent across all implementations.