algoadvance

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, find all the integers that appear twice.

You should implement the solution with O(n) time complexity and use only constant extra space.

Clarifying Questions

  1. Input Format:
    • Are there any other constraints on nums apart from its length and range of values?
    • Example: Should the elements always be positive integers?
  2. Output Format:
    • Should the output be a list of duplicated numbers, and does their order matter?

Assuming no further constraints are given, let’s proceed to the strategy.

Strategy

To achieve the requirements of O(n) time complexity and constant extra space, we can use the fact that the integers are in the range [1, n]. This allows us to use the array itself for marking the visited elements.

Here is the approach in detail:

  1. Iterate through the array: For each number, treat its absolute value as an index.
  2. Mark the visited numbers:
    • For each number num at index i, calculate the index index = abs(num) - 1 and negate the value at nums[index].
    • If nums[index] is already negative, it means the number abs(num) is a duplicate.
  3. Collect duplicates: If nums[index] is negative, add abs(num) to the result list.
  4. Restore the array (optional): If restoring the mutated array is necessary, restore it to its original state by making all values positive again.

Code

from typing import List

def findDuplicates(nums: List[int]) -> List[int]:
    duplicates = []

    for num in nums:
        index = abs(num) - 1
        
        if nums[index] < 0:
            duplicates.append(abs(num))
        else:
            nums[index] = -nums[index]

    # Optional: Restore the original array
    # for i in range(len(nums)):
    #     nums[i] = abs(nums[i])

    return duplicates

# Example usage
print(findDuplicates([4,3,2,7,8,2,3,1]))  # Output: [2, 3]
print(findDuplicates([1,1,2]))            # Output: [1]
print(findDuplicates([1]))                # Output: []

Time Complexity

This approach efficiently finds all duplicates in the list while adhering to the constraints of O(n) time complexity and constant extra space.

Try our interview co-pilot at AlgoAdvance.com