Find All Numbers Disappeared in an Array (LC 448)

Pattern: Cyclic Sort / In-place marking
Difficulty: Easy
Key Concept: Values live in [1, n] and indices are 0..n-1, so each value has a “home” index value - 1; either swap everyone home (cyclic sort) or mark visited homes (negative marking).

Problem Statement

You are given an integer array nums of length n. Every element satisfies 1 <= nums[i] <= n.

Return a list of all integers in the range [1, n] that do not appear in nums.

Input: int[] nums where nums.length == n and each value is in [1, n].
Output: List<Integer> (or any ordered collection) of every missing number in [1, n].

Example: nums = [4,3,2,7,8,2,3,1] → [5, 6] (numbers 1–4, 7, 8 appear; 5 and 6 never do).

---

1. Algorithm & Pseudocode

Brute force (HashSet)

build empty set S
for each x in nums:
    add x to S
create empty answer list
for k from 1 to n:
    if k not in S:
        add k to answer
return answer

Optimal A — Cyclic sort

i = 0
while i < n:
    correctIndex = nums[i] - 1
    if nums[i] != nums[correctIndex]:
        swap nums[i] with nums[correctIndex]
    else:
        i++

answer = empty list
for i from 0 to n-1:
    if nums[i] != i + 1:
        add (i + 1) to answer
return answer

Optimal B — Negative marking

for each index i from 0 to n-1:
    v = absolute value of nums[i]
    target = v - 1
    nums[target] = - absolute value of nums[target]

answer = empty list
for i from 0 to n-1:
    if nums[i] > 0:
        add (i + 1) to answer
return answer

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force works: If you remember every value you saw, you can scan 1..n and report gaps. A HashSet gives fast “have we seen this?” checks.

Why brute force costs extra space: The set holds up to n integers → O(n) auxiliary space.

Why cyclic sort fits: Each number x belongs at index x - 1. Swapping misplaced numbers into place groups duplicates: if two numbers want the same slot, swapping does nothing useful for that index, so you skip forward. After O(n) swaps total, any index i with nums[i] != i + 1 means i + 1 is missing (the value sitting there is a duplicate of something else).

Why negative marking works: Visiting value v means “v occurred,” so we flip the sign at index v - 1. If k never appears, index k - 1 is never flipped by a k, so it stays positive (unless you need to use abs when reading—see code). Indices that end positive correspond to missing i + 1.

Why both optimals are O(n) time and O(1) extra space: Only a constant number of pointers and swaps; the array itself holds the state.

---

3. The Dry Run

Sample: nums = [4, 3, 2, 7, 8, 2, 3, 1] → n = 8. Missing: 5 and 6.

Cyclic sort (key iterations)

Step	i	Array state (indices 0–7)	Action
0	0	[4,3,2,7,8,2,3,1]	nums[0]=4 → swap with index 3
1	0	[7,3,2,4,8,2,3,1]	nums[0]=7 → swap with index 6
2	0	[3,3,2,4,8,2,7,1]	nums[0]=3 → swap with index 2
3	0	[2,3,3,4,8,2,7,1]	nums[0]=2 → swap with index 1
4	0	[3,2,3,4,8,2,7,1]	nums[0]=3 equals nums[2] → i++
5	1	[3,2,3,4,8,2,7,1]	nums[1]=2 at home → i++
…	…	…	(continue until i reaches first “stuck” duplicate slots)
k	4	[3,2,3,4,8,2,7,1]	nums[4]=8 → swap with index 7
k+1	4	[3,2,3,4,1,2,7,8]	nums[4]=1 → swap with index 0
k+2	4	[1,2,3,4,3,2,7,8]	nums[4]=3 equals nums[2] → i++
end	—	[1,2,3,4,3,2,7,8]	Scan: index 4 has 3 (want 5), index 5 has 2 (want 6) → missing 5, 6

Negative marking (per index of original traversal order)

We use abs when reading; after each step the array may contain negatives.

Iteration i	Read value v (abs)	Mark index v-1	Array after mark (abbrev.)
0	4	negate nums[3]	[4,3,2,-7,8,2,3,1]
1	3	negate nums[2]	[4,3,-2,-7,8,2,3,1]
2	2	negate nums[1]	[4,-3,-2,-7,8,2,3,1]
3	7	negate nums[6]	[4,-3,-2,-7,8,2,-3,1]
4	8	negate nums[7]	[4,-3,-2,-7,8,2,-3,-1]
5	2	negate nums[1] (already ≤ 0)	unchanged
6	3	negate nums[2]	unchanged
7	1	negate nums[0]	[-4,-3,-2,-7,8,2,-3,-1]

Final scan: nums[4] > 0 and nums[5] > 0 → missing 5 and 6.

---

4. Java Solution

Brute Force

Uses HashSet to record present values, then checks 1..n.

Time: O(n) — one pass to fill the set, one pass to check each k.
Space: O(n) — the set.

import java.util.*;

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            seen.add(x);
        }
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        for (int k = 1; k <= n; k++) {
            if (!seen.contains(k)) {
                ans.add(k);
            }
        }
        return ans;
    }
}

Optimal

Cyclic sort (primary “pattern” solution):

import java.util.*;

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        int i = 0;
        while (i < n) {
            int correct = nums[i] - 1;
            if (nums[i] != nums[correct]) {
                int tmp = nums[i];
                nums[i] = nums[correct];
                nums[correct] = tmp;
            } else {
                i++;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            if (nums[j] != j + 1) {
                ans.add(j + 1);
            }
        }
        return ans;
    }
}

Negative marking (also O(n) time, O(1) extra space):

import java.util.*;

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int v = Math.abs(nums[i]);
            int idx = v - 1;
            if (nums[idx] > 0) {
                nums[idx] = -nums[idx];
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                ans.add(i + 1);
            }
        }
        return ans;
    }
}

---

5. The “Java vs. Others” Edge

• In-place tricks: Java has no built-in swap; use a temporary int. Same idea as C++.
• Math.abs: Essential for negative marking so you always read the original magnitude; Python also uses abs(), C++ std::abs.
• List<Integer> vs array: LeetCode often expects List<Integer>; building an ArrayList is idiomatic. Returning int[] would need a second pass to count missing first.
• Both cyclic sort and negative marking are valid “optimal” answers in interviews; cyclic sort reinforces the 1..n index mapping, while negative marking is often shorter to write.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	HashSet stores all distinct values (up to n).
Optimal (cyclic sort)	O(n)	O(1)	Each swap places at least one element; total swaps linear.
Optimal (negative marking)	O(n)	O(1)	Two passes; mutates signs in-place (restore if constraints change).