What is the brute force approach and complexity for Find All Numbers Disappeared in an Array?

For each k in 1..n, scan the array; collect the ones not found with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Find All Numbers Disappeared in an Array?

Swap each value v into index v − 1 until its home holds v, then every wrong slot i gives i + 1 with optimal time complexity O(N) and space complexity O(1).

Find All Numbers Disappeared in an Array

Q: How do you identify the pattern for Find All Numbers Disappeared in an Array?

Look for key signals in the prompt: "values in the range 1..n" indicates Every value fits an index — value v can live at index v − 1.; "some appear twice" indicates Duplicates will find their home already taken — the swap loop must stop on that.; "return all missing values" indicates Scan every slot after placement; do not stop at the first hole.; "no extra space" indicates No seen[] array — the input array must be the checklist..

Easy·LeetCode #448 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given an array nums of n integers, where every value is between 1 and n. Some values appear more than once, so some other values in 1..n do not appear at all.

Return all the values in 1..n that are missing from nums, in any order.

Follow-up: can you do it in O(N) time with no extra space? The returned list does not count as extra space.

Input

An integer array nums of length n with values in 1..n (duplicates allowed).

Output

A list of every value in 1..n that does not appear in nums.

Example 1

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

Output: [5, 6]

n = 8. The values 2 and 3 appear twice, which uses up the two places that 5 and 6 would have needed.

Example 2

Input: nums = [1, 1]

Output: [2]

n = 2. Only 1 appears, so 2 is missing.

Constraints

• n == nums.length
• 1 ≤ n ≤ 10^5
• 1 ≤ nums[i] ≤ n
• Follow-up: O(N) time, O(1) extra space (output not counted).

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“values in the range 1..n”

→ Every value fits an index — value v can live at index v − 1.

“some appear twice”

→ Duplicates will find their home already taken — the swap loop must stop on that.

“return all missing values”

→ Scan every slot after placement; do not stop at the first hole.

“no extra space”

→ No seen[] array — the input array must be the checklist.

Approach Complexity Ladder

Brute Force — search for every kO(N²)O(1)

For each k in 1..n, scan the array; collect the ones not found

Better — a seen[] checklistO(N)O(N)

Mark each value in a boolean array, then collect the unmarked ones

Optimal — cyclic sort (value v lives at index v − 1)O(N)O(1)

Swap each value v into index v − 1 until its home holds v, then every wrong slot i gives i + 1

Brute Force Intuition

For each k = 1, 2, …, n, scan the whole array. If k is never found, add it to the answer.

Recognition rule for this sub-pattern:

After placing every value at its home (index v − 1 for values 1..n; index v for 0..n, where n has no home), the first index without its own value is missing.

Remember this · Cyclic Sort

Trigger

Numbers in range 1..n or 0..n, find missing / duplicate / both, O(1) extra space.

Think

Can value v live at index v−1? Then put everyone home and look for squatters.

Key question

Where does value v belong, and when do I stop swapping?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Cyclic Sort translate into production architectures and low-level memory mechanics.

LLD Architecture