Find All Numbers Disappeared in an Array

LeetCode 448 | Difficulty: Easy

Easy

Problem Description

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

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

Example 2:

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

Constraints:

- `n == nums.length`

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

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

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Topics: Array, Hash Table

---

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.

---

Solutions

Solution 1: C# (Best: 364 ms)

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

Solution

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

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

    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] > 0)
        {
            ret.Add(i + 1);
        }
    }
    return ret;
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: This is a really easy problem if you decide to use additional memory. For those trying to write an initial solution using additional memory, think counters!

Hint 2: However, the trick really is to not use any additional space than what is already available to use. Sometimes, multiple passes over the input array help find the solution. However, there's an interesting piece of information in this problem that makes it easy to re-use the input array itself for the solution.

Hint 3: The problem specifies that the numbers in the array will be in the range [1, n] where n is the number of elements in the array. Can we use this information and modify the array in-place somehow to find what we need?