Find All Duplicates in an Array

LeetCode 442 | Difficulty: Medium

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

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

Input: nums = [1,1,2]
Output: [1]

Example 3:

Input: nums = [1]
Output: []

Constraints:

- `n == nums.length`

- `1 <= n <= 10^5`

- `1 <= nums[i] <= n`

- Each element in `nums` appears **once** or **twice**.

Topics: Array, Hash Table, Sorting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 368 ms)

Metric	Value
Runtime	368 ms
Memory	N/A
Date	2018-07-04

Solution

public class Solution {
    public IList<int> FindDuplicates(int[] nums) {
        HashSet<int> ret = new HashSet<int>();

    for (int i = 0; i < nums.Length; i++)
    {
        int val = Math.Abs(nums[i]) - 1;
        if (nums[val] > 0)
        {
            nums[val] = -nums[val];
        }
        else ret.Add(Math.Abs(nums[i]));
    }
    return ret.ToList();
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.