Find All Missing Numbers

📋

Problem

Imagine you have a list of student IDs from 1 to n, but some IDs are missing because students haven't registered yet. You want to find out which IDs are missing.

Given an array nums of n integers where nums[i] is in the range [1, n], some elements appear twice and others appear once. Find all the integers in the range [1, n] that do not appear in nums. Return the missing numbers in any order.

1 ≤ n ≤ 10^51 ≤ nums[i] ≤ nSome elements may appear twice, others once

Edge cases: All numbers present → output is empty listAll numbers missing except one → output is all except that oneArray with only one element → if missing, output that number

</>

IDE

def findDisappearedNumbers(nums: list[int]) -> list[int]:public List<Integer> findDisappearedNumbers(int[] nums)vector<int> findDisappearedNumbers(vector<int>& nums)function findDisappearedNumbers(nums)

def findDisappearedNumbers(nums):
    # Write your solution here
    pass

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> findDisappearedNumbers(vector<int>& nums) {
    // Write your solution here
    return {};
}

function findDisappearedNumbers(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,2,3,4]Returning all numbers instead of only missing ones; possibly returning full range without filtering.✅ After cyclic sort, return only numbers i+1 where nums[i] != i+1, not the entire range.

Wrong: [5,6,7,8]Returning duplicates or numbers present in array as missing; incorrect condition in final check.✅ Check nums[i] != i+1 strictly to identify missing numbers; do not include duplicates or present numbers.

Wrong: Infinite loop or timeoutSwapping duplicates repeatedly without a condition to break loop.✅ Add condition to skip swap if nums[i] == nums[nums[i]-1] to prevent infinite loops.

Wrong: [ ] for input [2]Fails to detect missing number when single element is not 1.✅ After sorting, check all indices for nums[i] != i+1 and return missing numbers accordingly.

Wrong: [5,6,7]Incorrect handling of array length vs max element; missing numbers beyond max element not detected.✅ Use n = len(nums) consistently and check all numbers from 1 to n for presence.

✓

Test Cases

Try testing your code on empty and single-element arrays to catch base case bugs.

Consider how duplicates and boundary lengths might break your logic; add checks accordingly.

Think about the time complexity of your solution; large inputs require O(n) time.

t1_01basic

Input{"nums":[4,3,2,7,8,2,3,1]}

Expected[5,6]

⏱ Performance - must finish in 2000ms

Numbers 5 and 6 are missing from the array since all others from 1 to 8 appear.

💡 Consider placing each number at its correct index to identify missing ones.

💡 Use cyclic sort to rearrange elements so that nums[i] == i+1 where possible.

💡 After sorting, missing numbers are those indices i where nums[i] != i+1.

Why it failed: Failed basic case: likely incorrect swapping or index calculation. Fix by ensuring swap places nums[i] at nums[nums[i]-1] correctly.

✓ Correctly identifies missing numbers using cyclic sort.

t1_02basic

Input{"nums":[1,1]}

Expected[2]

⏱ Performance - must finish in 2000ms

Number 2 is missing; array has duplicates of 1 only.

💡 Duplicates cause some numbers to be missing; identify by checking final positions.

💡 After cyclic sort, numbers not at their correct index indicate missing values.

💡 Return all indices i+1 where nums[i] != i+1 to find missing numbers.

Why it failed: Fails to handle duplicates properly; fix by skipping swaps when nums[i] == nums[nums[i]-1] to avoid infinite loops.

✓ Handles duplicates correctly and finds missing numbers.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty array means no numbers, so no missing numbers in range 1 to 0.

💡 Check how your code handles empty input arrays.

💡 Ensure no index errors occur when nums is empty.

💡 Return empty list immediately if input is empty.

Why it failed: Fails on empty input due to index errors or no base case; fix by adding check for empty array before processing.

✓ Correctly returns empty list for empty input.

t2_02edge

Input{"nums":[1]}

Expected[]

⏱ Performance - must finish in 2000ms

Single element array with number 1 means no missing numbers.

💡 Single element arrays are a boundary case; verify handling.

💡 Check if your code correctly identifies no missing numbers when all present.

💡 Return empty list if all numbers from 1 to n appear.

Why it failed: Fails single element present case by incorrectly reporting missing numbers; fix by verifying final positions after sorting.

✓ Correctly returns empty list when all numbers present.

t2_03edge

Input{"nums":[2]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single element array with number 2 means number 1 is missing.

💡 Check single element arrays where the element is not 1.

💡 After cyclic sort, missing numbers are those indices where nums[i] != i+1.

💡 Return list of missing numbers accordingly.

Why it failed: Fails single element missing case by not detecting missing 1; fix by checking all indices after sorting.

✓ Correctly identifies missing number in single element array.

t3_01corner

Input{"nums":[2,2,2,2]}

Expected[1,3,4]

⏱ Performance - must finish in 2000ms

All elements are duplicates of 2; missing numbers are 1, 3, and 4.

💡 Duplicates can cause infinite swaps if not handled properly.

💡 Avoid swapping when nums[i] == nums[nums[i]-1] to prevent infinite loops.

💡 Check for duplicates before swapping to ensure termination.

Why it failed: Infinite loop or incorrect output due to swapping duplicates repeatedly; fix by adding condition to skip swap if nums[i] == nums[nums[i]-1]. This is the duplicates infinite loop test.

✓ Handles duplicates correctly without infinite loops.

t3_02corner

Input{"nums":[1,2,2,4]}

Expected[3]

⏱ Performance - must finish in 2000ms

Number 3 is missing; duplicates of 2 present.

💡 Check that duplicates do not cause missing numbers to be overlooked.

💡 After cyclic sort, missing numbers correspond to indices where nums[i] != i+1.

💡 Return all such indices + 1 as missing numbers.

Why it failed: Fails to detect missing number due to incorrect handling of duplicates; fix by ensuring final check for nums[i] != i+1 after sorting.

✓ Correctly finds missing number despite duplicates.

t3_03corner

Input{"nums":[4,3,2,7,8,2,3,1,9]}

Expected[5,6]

⏱ Performance - must finish in 2000ms

Array length 9 with numbers 1 to 9; missing 5 and 6.

💡 Check that your code handles arrays where n > max(nums) correctly.

💡 Ensure cyclic sort uses array length n for range checks.

💡 Return missing numbers from 1 to n not present in nums.

Why it failed: Fails when array length exceeds max element; fix by using n = len(nums) consistently for range and indexing. This is the boundary length test.

✓ Handles array length and range correctly.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(n) time complexity; must complete within 2 seconds.

💡 Optimal solution runs in O(n) time using cyclic sort.

💡 Avoid nested loops or extra space proportional to n.

💡 Use in-place swaps and single pass to achieve required performance.

Why it failed: TLE due to O(n^2) or higher complexity; fix by implementing O(n) cyclic sort approach without nested loops.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. You are given an array containing n distinct numbers taken from the range 0 to n. Exactly one number from this range is missing in the array. Which algorithmic approach guarantees finding the missing number in O(n) time and O(1) space without using extra data structures?

easy

A. Applying a dynamic programming approach to build a state table of present numbers

B. Sorting the array and then scanning for the missing number

C. Using a hash set to track presence of numbers and then checking which is missing

D. Cyclic sort to place each number at its correct index, then scanning for the mismatch

Solution

1. Step 1: Understand problem constraints

   The array contains numbers from 0 to n with one missing; all are distinct.

2. Step 2: Identify approach with O(n) time and O(1) space

   Cyclic sort places each number at its index in one pass, then a single scan finds the missing number efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cyclic sort rearranges in-place with linear time and constant space [OK]

Hint: Cyclic sort matches numbers to indices in-place [OK]

Common Mistakes:

• Assuming sorting is always O(n log n)
• Thinking hash sets use O(1) space
• Confusing DP with presence checking

2. Consider the following buggy code for finding the duplicate number. Which line contains the subtle bug that can cause an infinite loop or incorrect result?

medium

A. Line 7: else: i += 1

B. Line 4: if nums[i] == nums[correct_index]:

C. Line 9: else: nums[i], nums[correct_index] = nums[correct_index], nums[i]

D. Line 2: while i < len(nums):

Solution

1. Step 1: Compare with correct code condition

   The condition should be if nums[i] != nums[correct_index] to decide when to swap.

2. Step 2: Identify effect of wrong condition

   Using == causes swapping only when elements are equal, leading to infinite loops or missed duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect condition breaks cyclic sort logic [OK]

Hint: Swap only when elements differ, not when equal [OK]

Common Mistakes:

• Reversing the swap condition causing infinite loops
• Incrementing index incorrectly
• Swapping elements in wrong order

3. What is the time complexity of the optimal cyclic sort approach for finding the first missing positive integer in an array of length n?

medium

A. O(n) amortized because each swap places an element correctly

B. O(n) because each element is swapped at most once

C. O(n log n) due to sorting-like swaps

D. O(n^2) because of nested while loops inside the for loop

Solution

1. Step 1: Analyze the loops

   The outer loop runs n times, and the inner while loop swaps elements to their correct positions.

2. Step 2: Understand swap frequency

   Each element can be swapped at most once to its correct position, so total swaps ≤ n, making the inner loop amortized O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized analysis confirms O(n) time complexity [OK]

Hint: Each element swapped at most once -> O(n) amortized [OK]

Common Mistakes:

• Assuming nested loops mean O(n^2)
• Confusing amortized with worst-case per iteration
• Thinking swaps are unlimited causing O(n log n)

4. What is the time complexity of the optimal cyclic sort approach for finding the duplicate and missing numbers in an array of size n?

medium

A. O(n) with additional O(n) space for frequency tracking

B. O(n log n) due to sorting operations

C. O(n^2) in worst case due to nested swaps

D. O(n) because each element is swapped at most once

Solution

1. Step 1: Identify the loops and swaps

   The while loop runs at most n times, each swap places an element correctly, so total swaps ≤ n.

2. Step 2: Confirm no nested repeated work

   Each element is swapped at most once, so total operations are linear in n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear time complexity confirmed by single pass swaps [OK]

Hint: Each element swapped once -> O(n) time [OK]

Common Mistakes:

• Assuming sorting cost O(n log n)
• Thinking swaps can be quadratic
• Confusing extra space usage

5. If the input array can contain numbers reused multiple times (duplicates can appear more than once), which modification to the cyclic sort approach correctly finds one duplicate and one missing number?

hard

A. Use a frequency array to count occurrences instead of cyclic sort

B. Modify cyclic sort to skip swapping when nums[i] == nums[correct] to avoid infinite loops

C. Run cyclic sort multiple times until no swaps occur

D. Sort the array and scan for duplicates and missing numbers

Solution

1. Step 1: Understand the problem extension

   Multiple duplicates break naive cyclic sort because repeated swaps cause infinite loops.

2. Step 2: Modify cyclic sort to skip swapping when duplicate detected

   Adding a check to skip swapping if nums[i] == nums[correct] prevents infinite loops and still finds mismatch.

3. Step 3: Contrast other options

   Frequency array uses extra space, multiple runs are inefficient, sorting is O(n log n).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Skipping swaps on duplicates fixes infinite loop in cyclic sort [OK]

Hint: Skip swaps when duplicate detected to avoid infinite loops [OK]

Common Mistakes:

• Assuming cyclic sort works unchanged with multiple duplicates
• Relying on multiple passes instead of fixing swap condition
• Ignoring space constraints by using frequency arrays