Log inSign up
easyLeetCodeNot Started

Find All Numbers Disappeared in an Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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.

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

Example 1 · Standard Missing Numbers:

Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [5, 6]
Explanation: The numbers in range [1, 8] are 1, 2, 3, 4, 5, 6, 7, 8. The numbers 5 and 6 are missing from the array.

Example 2 · Two-element Array with Duplicate:

Input: nums = [1, 1]
Output: [2]
Explanation: For n = 2, range is [1, 2]. 2 is missing, so we return [2].

Example 3 · All Numbers Present:

Input: nums = [2, 1, 3]
Output: []
Explanation: All numbers from 1 to 3 are present, so no number is missing. Output is [].

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n
  • Some elements appear twice and others appear once.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 0-based vs 1-based indexing relationships (value v maps to index v - 1)
  • Using array elements simultaneously as data and visited flags
  • Absolute value operations (abs) to read original values after negation

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 'Index As Hash Key' pattern for arrays with elements in range [1, N].
  • Use in-place sign negation to store visited state while preserving the original number using absolute values.
  • Derive why positive elements after pass 1 correspond to missing numbers: missing = index + 1.
  • Write clean, production-ready code in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • When numbers are in range [1, N] and O(1) extra space is requested -> Use the array itself as a hash table by negating nums[abs(val) - 1].
  • If values can be modified and restored -> Negate signs on first pass, collect positive indices on second pass.
  • If array is read-only -> Use Cyclic Sort or a Hash Set (O(N) space).

Connected Patterns:

Index As Hash KeyCyclic SortFind All Duplicates in an ArrayFirst Missing Positive

1. Brute Force — Linear Search for Each 1..N

Intuition

For every integer x from 1 to N, scan the array to verify if x exists. If not found, add x to the result list.

Algorithm

  1. Initialize an empty list result.
  2. Loop x from 1 to N.
  3. Set found = false.
  4. Inner loop through nums: if num == x, set found = true and break.
  5. If found is false, append x to result.
  6. Return result.

Brute Force 1..N Membership Linear Scans

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 3, 2, 7, 8, 2, 3, 1]
Current operationSTEP 1 OF 6
Phase 1 — 1 is present Do not add to missing list: Step 1: Test integer x = 1
Visual state
Values and pointers at this exact step
array
S
4
3
2
7
8
2
3
1
0
1
2
3
4
5
6
7
↑ Scan for x=1
Variables at this step
x
1
Found
true
missing
[]
Check / comparison
Search for x = 1 in nums. Found at index 7 (nums[7] == 1).
Decision / next transition
1 is present. Do not add to missing list.
Why this step matters

Phase 1 — 1 is present Do not add to missing list: Step 1: Test integer x = 1. Linear scan finds 1 at index 7. Not missing.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Brute Force: Check each number from 1 to N
6vector<int> findDisappearedNumbers(const vector<int>& nums) {
7 int n = nums.size();
8 vector<int> result;
9
10 for (int x = 1; x <= n; x++) {
11 bool found = false;
12 for (int num : nums) {
13 if (num == x) {
14 found = true;
15 break;
16 }
17 }
18 if (!found) {
19 result.push_back(x); // x was not found
20 }
21 }
22 return result;
23}
24
25int main() {
26 vector<int> nums = {4, 3, 2, 7, 8, 2, 3, 1};
27 vector<int> missing = findDisappearedNumbers(nums);
28
29 cout << "Missing: [";
30 for (int i = 0; i < (int)missing.size(); i++) {
31 cout << missing[i] << (i + 1 < (int)missing.size() ? ", " : "");
32 }
33 cout << "]" << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N²) — Outer loop runs N times (for x = 1 to N). Inner loop scans N elements. Total operations = N × N = O(N²).
  • Space complexity: O(1) auxiliary — Output list is not counted as auxiliary space. No additional data structures are used.

Why Brute Force Doesn't Scale:

For N = 100,000, checking every number takes 100,000 × 100,000 = 10,000,000,000 operations (10 billion checks), causing TLE.

Key Insight: We are given that numbers are in [1, N]. This means array indices (0 to N - 1) directly correspond to the numbers (1 to N). By negating the value at index (val - 1), we record presence in-place without needing any extra memory.

For N = 105: Brute force takes ~10B ops (TLE). In-place negation takes 2N = 200K ops (~2ms).

2. Better — Hash Set Lookup

Intuition

Store all array elements in a Hash Set for O(1) membership checking, then iterate from 1 to N and collect absent numbers.

Algorithm

  1. Insert all elements of nums into a Hash Set seen.
  2. Initialize an empty list result.
  3. Loop x from 1 to N.
  4. If x is not in seen, append x to result.
  5. Return result.

Boolean Seen Array / Hash Set

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 3, 2, 7, 8, 2, 3, 1]
Current operationSTEP 1 OF 6
Phase 1 — Begin first pass to mark presence: Step 1: Create a boolean array seen of size N initialized to false
Visual state
Values and pointers at this exact step
array
S
4
3
2
7
8
2
3
1
0
↑ Init seen[8]
1
2
3
4
5
6
7
Variables at this step
seen
[F, F, F, F, F, F, F, F]
Check / comparison
Allocate seen = [F, F, F, F, F, F, F, F] for numbers 1..8.
Decision / next transition
Begin first pass to mark presence.
Why this step matters

Phase 1 — Begin first pass to mark presence: Step 1: Create a boolean array seen of size N initialized to false.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_set>
3#include <vector>
4using namespace std;
5
6// Better: Hash Set
7vector<int> findDisappearedNumbers(const vector<int>& nums) {
8 unordered_set<int> seen(nums.begin(), nums.end());
9 vector<int> result;
10 int n = nums.size();
11
12 for (int x = 1; x <= n; x++) {
13 if (seen.find(x) == seen.end()) {
14 result.push_back(x); // Missing number
15 }
16 }
17 return result;
18}
19
20int main() {
21 vector<int> nums = {4, 3, 2, 7, 8, 2, 3, 1};
22 vector<int> missing = findDisappearedNumbers(nums);
23
24 cout << "Missing: [";
25 for (int i = 0; i < (int)missing.size(); i++) {
26 cout << missing[i] << (i + 1 < (int)missing.size() ? ", " : "");
27 }
28 cout << "]" << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N) — Building the Hash Set takes O(N) time. Iterating from 1 to N with O(1) set lookups takes O(N) time. Total time = O(N).
  • Space complexity: O(N) — The Hash Set stores up to N unique integers, requiring O(N) auxiliary space.

3. Optimal — In-Place Index Negation

Intuition

Treat the array itself as a hash table. When encountering number v, negate nums[abs(v) - 1]. Positive elements on pass 2 indicate missing numbers.

Algorithm

  1. Iterate with index i from 0 to N - 1.
  2. Calculate mapped index idx = abs(nums[i]) - 1.
  3. If nums[idx] > 0, negate it: nums[idx] = -nums[idx].
  4. In a second pass from i = 0 to N - 1, if nums[i] > 0, append i + 1 to result.
  5. Return result.

In-Place Negative Sign Value-As-Index Marking

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [4, 3, 2, 7, 8, 2, 3, 1]
Current operationSTEP 1 OF 8
Phase 1 — Begin marking pass: Step 1: Since all values are in [1, n], for any value v, we can mark index v - 1 as visited by flipping its sign negative: nums[v - 1] = -abs(nums[v - 1])
Visual state
Values and pointers at this exact step
array
S
4
3
2
7
8
2
3
1
0
↑ nums array as hash table
1
2
3
4
5
6
7
Variables at this step
Technique
Negative Sign In-Place Marking
Auxiliary Space
O(1)
Check / comparison
Aha! Invariant: Values are in 1..N. We can use the sign of nums[abs(val) - 1] as an in-place visited flag!
Decision / next transition
Begin marking pass.
Why this step matters

Phase 1 — Begin marking pass: Step 1: Since all values are in [1, n], for any value v, we can mark index v - 1 as visited by flipping its sign negative: nums[v - 1] = -abs(nums[v - 1]).

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <cmath>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6// Optimal: In-Place Sign Negation
7vector<int> findDisappearedNumbers(vector<int>& nums) {
8 int n = nums.size();
9
10 // Pass 1: Mark visited indices negative
11 for (int i = 0; i < n; i++) {
12 int idx = abs(nums[i]) - 1; // Map value to 0-based index
13 if (nums[idx] > 0) {
14 nums[idx] = -nums[idx]; // Mark as seen
15 }
16 }
17
18 // Pass 2: Collect indices that remained positive
19 vector<int> result;
20 for (int i = 0; i < n; i++) {
21 if (nums[i] > 0) {
22 result.push_back(i + 1); // (i + 1) was never visited
23 }
24 }
25 return result;
26}
27
28int main() {
29 vector<int> nums = {4, 3, 2, 7, 8, 2, 3, 1};
30 vector<int> missing = findDisappearedNumbers(nums);
31
32 cout << "Missing: [";
33 for (int i = 0; i < (int)missing.size(); i++) {
34 cout << missing[i] << (i + 1 < (int)missing.size() ? ", " : "");
35 }
36 cout << "]" << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N) — Two linear passes of length N: Pass 1 marks visited indices in O(N) time. Pass 2 scans for positive numbers in O(N) time. Total time = 2N = O(N).
  • Space complexity: O(1) auxiliary — Modifications are performed directly in-place within the input array. The returned output list does not count towards auxiliary space per problem specification.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear Search Each 1..NO(N²)O(1)For each integer x from 1 to N, scan the entire array to check if x is present.N separate scans of array of size N.
2.Better — Hash Set LookupO(N)O(N)Add all elements to a Hash Set, then iterate 1 to N and collect numbers not in set.Extra memory when values can be mapped in-place.
3.Optimal — In-Place Sign NegationOptimalO(N)O(1) auxNegate nums[abs(val) - 1] to mark presence. Indices that remain positive represent missing values.Optimal.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to use Math.abs() when reading nums[i], leading to negative index out of bounds exceptions.

Pitfall 2:

Negating without checking nums[idx] > 0, which accidentally flips negative numbers back to positive when duplicates exist.

Pitfall 3:

Returning i instead of i + 1 in Pass 2 (forgetting the 0-based to 1-based shift).

Crucial Edge Cases to Validate:

  • Array with duplicate identical values (nums = [1, 1]) -> returns [2].
  • Array where all numbers 1..N are present (nums = [1, 2, 3]) -> returns [].
  • Array where multiple numbers are missing (nums = [2, 2, 2, 2]) -> returns [1, 3, 4].
  • Single element array (nums = [1]) -> returns [].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the Hash Set approach (O(N) time, O(N) space) first in 20 seconds, then immediately transition to the O(1) space in-place sign negation trick.
  2. Highlight the importance of abs() to safely read elements that were previously negated.
  3. Emphasize that the check if (nums[idx] > 0) prevents duplicates from double-flipping signs back to positive.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Find All Numbers Disappeared in an Array?

2.Why is the brute force approach suboptimal for large inputs in Find All Numbers Disappeared in an Array?

3.Which data structure or technique enables the optimal solution for Find All Numbers Disappeared in an Array?

Back to DSA Sheet