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.