Question

You are given an array nums containing n integers, where each value is between 1 and n (inclusive). Your task is to find all the elements that appear more than once in the array.

Write a function findDuplicates(nums: List[int]) -> List[int] that returns a list of all the duplicate elements in the given array.

Example

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
Explanation: The elements 2 and 3 both appear twice in the array.

Constraints

• The length of the array will be between 1 and 10^5.
• Each element in the array will be between 1 and n (inclusive).

Answer

To find all the duplicates in the array, we can utilize the fact that the values in the array are between 1 and n. We will traverse the array and use the indices of the values to mark them as visited.

Here are the steps to solve the problem:

1. Create an empty dictionary visited to keep track of the visited values.
2. Create an empty list duplicates to store the duplicate elements.
3. Traverse the array nums and for each element num, do the following:
   • If num is not in the visited dictionary, add it as a key with a value of True to indicate that it has been visited.
   • If num is already in the visited dictionary and its value is True, append num to the duplicates list.
   • Set the value of num in the visited dictionary to False to mark it as visited.
4. Return the duplicates list as the result.

Here is the implementation of the function in Python:

from typing import List

def findDuplicates(nums: List[int]) -> List[int]:
    visited = {}   # Step 1
    duplicates = []   # Step 2
    for num in nums:   # Step 3
        if num not in visited:
            visited[num] = True
        elif visited[num] == True:
            duplicates.append(num)
        visited[num] = False
    return duplicates   # Step 4

The time complexity of this solution is O(n), where n is the length of the array nums. This is because we traverse the array once and perform constant time operations to check for duplicates and mark visited values.