{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Find All Duplicates in an Array – Solution & Complexity

Interview solutions
/
Find All Duplicates in an Array

Solution Walkthrough

  1. Step 1: Use the problem guarantees

    Every number is between 1 and n, and each value appears at most twice. That means you can either count what you have seen with extra memory, or reuse the input array itself as a visitation map by jumping to index value - 1.

  2. Step 2: Warm up with a hash-set solution

    Scan the array once, track values already seen, and append a value when it appears the second time. Because the final answer must be deterministic and sorted, sort the collected duplicates before returning them.

    def find_duplicates(nums: list[int]) -> list[int]:
    seen = set()
    duplicates = []

    for num in nums:
        if num in seen:
            duplicates.append(num)
        else:
            seen.add(num)

    duplicates.sort()
    return duplicates

  3. Step 3: Reuse the array as the visited structure

    For each value val, look at index abs(val) - 1. If that slot is still positive, negate it to mark that val has been seen once. If that slot is already negative, then val is appearing for the second time, so it belongs in the answer.

  4. Step 4: Final in-place marking solution

    This is the classic follow-up solution: detect duplicates in one pass by negating nums[abs(val) - 1], collect values that hit an already-negative slot, then sort the output so the returned array is always in ascending order.

    def find_duplicates(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] *= -1

    duplicates.sort()
    return duplicates

FAQ

See also

Practice Find All Duplicates in an Array online (run code in the browser)Valid Sudoku solution (medium)3Sum solution (medium)3Sum Closest solution (medium)Best Time to Buy and Sell Stock solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?