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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find All Duplicates in an Array

Number: 442

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Meta, Amazon, TikTok, Oracle, Apple, Bloomberg, Pocket Gems

Problem Description

Given an integer array nums of length n where all the integers are in the range [1, n] and each element appears either once or twice, return an array of all the integers that appear exactly twice. The solution must run in O(n) time and use only constant extra space (excluding the output array).

Key Insights

  • The elements are in the range [1, n], meaning each number can be mapped to an index in the array.
  • Each element appears at most twice. This guarantees that if we see a repeated occurrence, it is exactly the duplicate we need.
  • The problem constraints suggest using the array itself for bookkeeping to achieve constant extra space.
  • A common trick is to use the sign flipping technique: negating the element at the corresponding index.
  • When encountering a number whose corresponding index is already negative, it indicates that the number has been seen before, and hence it's a duplicate.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1) (excluding the space needed for the output array)

Solution

We iterate through the array and for each number, we calculate an index using the absolute value of the number minus one. Then, we check the sign of the number at that index:

  • If it is positive, we mark it as seen by making it negative.
  • If it is already negative, it means we have encountered this number before and we add it to our result list. Using this in-place sign flipping technique leverages the constraints on the values and maintains constant extra space while scanning the array only once.

Code Solutions

def findDuplicates(nums):
    # List to store the duplicate numbers
    result = []
    # Iterate over each number in the array
    for num in nums:
        index = abs(num) - 1  # map number to index (0-indexed)
        # If the number at this index is already negative, it's a duplicate
        if nums[index] < 0:
            result.append(abs(num))
        else:
            # Mark the number as seen by flipping the sign
            nums[index] = -nums[index]
    return result
← Back to All Questions