We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find All Duplicates in an Array

Difficulty: Medium

Problem Description

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, excluding the space needed to store the output.

Key Insights

  • The integers in nums are within the range [1, n], which allows for index manipulation.
  • Each integer appears at most twice, enabling us to use the array itself to mark visited numbers.
  • We can leverage the property of negative marking to identify duplicates without using additional space.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (excluding the output)

Solution

To solve the problem, we can use the input array itself to keep track of the numbers we have seen. For each number in the array, we can mark its corresponding index as visited by negating the value at that index. If we encounter a number whose corresponding index is already negative, it means that number has been seen before and is a duplicate.

The algorithm involves iterating through the array once and checking/marking indices accordingly.

Code Solutions

def findDuplicates(nums):
    duplicates = []
    for num in nums:
        index = abs(num) - 1  # Get the index for the current number
        if nums[index] < 0:  # If the value at that index is negative, it's a duplicate
            duplicates.append(abs(num))
        else:
            nums[index] = -nums[index]  # Mark the number as seen by negating the value
    return duplicates
← Back to All Questions