Find All Missing Numbers

🎯

Find All Missing Numbers

easyCYCLIC_SORTAmazonFacebookGoogle

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.

💡 This problem is about identifying missing elements in a sequence where numbers are supposed to be from 1 to n. Beginners often struggle because they try to use extra space or sorting without realizing an in-place cyclic sort can solve it efficiently.

📋

Problem Statement

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

💡

Example

Input"[4,3,2,7,8,2,3,1]"

Output[5,6]

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

• All numbers present → output is empty list
• All numbers missing except one → output is all except that one
• Array with only one element → if missing, output that number
• Array with duplicates of the same number → missing numbers are all others

⚠️

Common Mistakes

Swapping without checking if target position already has correct number

Infinite loop or incorrect placement causing wrong output

✅ Add condition to swap only if nums[i] != nums[correct]

Using extra space but forgetting to adjust indices by -1

Index out of range error or wrong missing numbers

✅ Always subtract 1 from number to map to zero-based index

Not handling duplicates properly in cyclic sort

Incorrect swaps or infinite loops

✅ Check if nums[i] == nums[correct] before swapping to avoid duplicates

Returning indices instead of numbers as missing

Wrong output values that don't match problem requirements

✅ Add 1 to indices when collecting missing numbers

Sorting with default sort in JavaScript without numeric comparator

Lexicographical sort leads to wrong order and incorrect missing numbers

✅ Use nums.sort((a,b) => a - b) for numeric sorting

🧠

Brute Force (Check Presence Using Extra Space)

💡 This approach exists to build intuition by directly checking which numbers are missing using extra memory, helping beginners understand the problem's requirements before optimizing.

Intuition

We can create a boolean array to mark which numbers from 1 to n appear in the input. Then, any number not marked is missing.

Algorithm

1. Create a boolean array of size n initialized to False.
2. Traverse the input array and mark the boolean array True at index corresponding to each number.
3. Traverse the boolean array to collect indices where value is False (these indices + 1 are missing numbers).
4. Return the collected missing numbers.

💡 This algorithm is straightforward but uses extra space, which is not optimal but helps understand the problem.

</>

Code

def findDisappearedNumbers(nums):
    n = len(nums)
    present = [False] * n
    for num in nums:
        present[num - 1] = True
    missing = []
    for i in range(n):
        if not present[i]:
            missing.append(i + 1)
    return missing

# Driver code
if __name__ == '__main__':
    print(findDisappearedNumbers([4,3,2,7,8,2,3,1]))  # Output: [5,6]

Line Notes

n = len(nums)Determine the size of the input array to create a presence tracker.

present = [False] * nInitialize a boolean list to track which numbers appear.

for num in nums:Iterate over each number to mark its presence.

present[num - 1] = TrueMark the index corresponding to the number as True to indicate presence.

missing = []Prepare a list to collect missing numbers.

for i in range(n):Check each position in the presence list to find missing numbers.

if not present[i]:If a number is not present, add it to the missing list.

missing.append(i + 1)Add the missing number (index + 1) to the result.

import java.util.*;
public class Solution {
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        boolean[] present = new boolean[n];
        for (int num : nums) {
            present[num - 1] = true;
        }
        List<Integer> missing = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!present[i]) {
                missing.add(i + 1);
            }
        }
        return missing;
    }

    public static void main(String[] args) {
        System.out.println(findDisappearedNumbers(new int[]{4,3,2,7,8,2,3,1})); // Output: [5, 6]
    }
}

Line Notes

int n = nums.length;Get the length of the input array for iteration and presence array size.

boolean[] present = new boolean[n];Create a boolean array to track presence of numbers.

for (int num : nums)Loop through each number in the input array.

present[num - 1] = true;Mark the number's presence in the boolean array.

List<Integer> missing = new ArrayList<>();Initialize list to store missing numbers.

for (int i = 0; i < n; i++)Iterate over the presence array to find missing numbers.

if (!present[i])Check if the number corresponding to index i is missing.

missing.add(i + 1);Add the missing number to the result list.

#include <iostream>
#include <vector>
using namespace std;

vector<int> findDisappearedNumbers(vector<int>& nums) {
    int n = nums.size();
    vector<bool> present(n, false);
    for (int num : nums) {
        present[num - 1] = true;
    }
    vector<int> missing;
    for (int i = 0; i < n; i++) {
        if (!present[i]) {
            missing.push_back(i + 1);
        }
    }
    return missing;
}

int main() {
    vector<int> nums = {4,3,2,7,8,2,3,1};
    vector<int> result = findDisappearedNumbers(nums);
    for (int num : result) cout << num << " "; // Output: 5 6
    cout << endl;
    return 0;
}

Line Notes

int n = nums.size();Get the size of the input vector for iteration and presence vector size.

vector<bool> present(n, false);Initialize a boolean vector to track presence of numbers.

for (int num : nums)Loop through each number in the input vector.

present[num - 1] = true;Mark the presence of the number in the boolean vector.

vector<int> missing;Prepare a vector to store missing numbers.

for (int i = 0; i < n; i++)Iterate over the presence vector to find missing numbers.

if (!present[i])Check if the number corresponding to index i is missing.

missing.push_back(i + 1);Add the missing number to the result vector.

function findDisappearedNumbers(nums) {
    const n = nums.length;
    const present = new Array(n).fill(false);
    for (const num of nums) {
        present[num - 1] = true;
    }
    const missing = [];
    for (let i = 0; i < n; i++) {
        if (!present[i]) {
            missing.push(i + 1);
        }
    }
    return missing;
}

// Test
console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // Output: [5,6]

Line Notes

const n = nums.length;Determine the length of the input array for iteration and presence array size.

const present = new Array(n).fill(false);Create a boolean array to track presence of numbers.

for (const num of nums)Iterate over each number in the input array.

present[num - 1] = true;Mark the number's presence in the boolean array.

const missing = [];Initialize an array to collect missing numbers.

for (let i = 0; i < n; i++)Loop through the presence array to find missing numbers.

if (!present[i])Check if the number corresponding to index i is missing.

missing.push(i + 1);Add the missing number to the result array.

⏱

Complexity

TimeO(n)

SpaceO(n)

We iterate over the input array once to mark presence and once over the boolean array to find missing numbers, each O(n). The extra space is O(n) for the boolean array.

💡 For n=100,000, this means about 200,000 operations and 100,000 extra booleans, which is acceptable but not optimal.

Interview Verdict: Accepted but not optimal

This approach works but uses extra memory, which can be improved by in-place algorithms.

🧠

Sorting and Linear Scan

💡 Sorting the array helps organize numbers so missing ones can be found by checking gaps, teaching the value of ordering before searching.

Intuition

Sort the array, then scan from 1 to n to find which numbers are missing by comparing expected and actual values.

Algorithm

1. Sort the input array.
2. Initialize a pointer to track expected number starting at 1.
3. Traverse the sorted array, for each number, add all missing numbers between expected and current number.
4. After traversal, add any remaining numbers up to n.
5. Return the collected missing numbers.

💡 Sorting simplifies the problem but costs time; scanning for gaps is intuitive.

</>

Code

def findDisappearedNumbers(nums):
    nums.sort()
    missing = []
    expected = 1
    for num in nums:
        while expected < num:
            missing.append(expected)
            expected += 1
        if expected == num:
            expected += 1
    while expected <= len(nums):
        missing.append(expected)
        expected += 1
    return missing

# Driver code
if __name__ == '__main__':
    print(findDisappearedNumbers([4,3,2,7,8,2,3,1]))  # Output: [5,6]

Line Notes

nums.sort()Sort the array to bring numbers in order for gap detection.

missing = []Initialize list to collect missing numbers.

expected = 1Start checking from number 1 upwards.

for num in nums:Traverse sorted numbers to find missing gaps.

while expected < num:Add all missing numbers between expected and current number.

missing.append(expected)Add missing number to the list.

expected += 1Move expected pointer forward.

if expected == num:If current number matches expected, move expected forward.

while expected <= len(nums):Add any missing numbers after the last element.

return missingReturn the list of missing numbers.

import java.util.*;
public class Solution {
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        Arrays.sort(nums);
        List<Integer> missing = new ArrayList<>();
        int expected = 1;
        for (int num : nums) {
            while (expected < num) {
                missing.add(expected);
                expected++;
            }
            if (expected == num) {
                expected++;
            }
        }
        while (expected <= nums.length) {
            missing.add(expected);
            expected++;
        }
        return missing;
    }

    public static void main(String[] args) {
        System.out.println(findDisappearedNumbers(new int[]{4,3,2,7,8,2,3,1})); // Output: [5, 6]
    }
}

Line Notes

Arrays.sort(nums);Sort the input array to detect missing numbers by gaps.

List<Integer> missing = new ArrayList<>();Prepare list to store missing numbers.

int expected = 1;Initialize expected number to 1.

for (int num : nums)Traverse sorted array to find missing numbers.

while (expected < num)Add all missing numbers between expected and current number.

missing.add(expected);Add missing number to the list.

expected++;Increment expected number.

if (expected == num)If current number matches expected, move expected forward.

while (expected <= nums.length)Add any missing numbers after the last element.

return missing;Return the list of missing numbers.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> findDisappearedNumbers(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> missing;
    int expected = 1;
    for (int num : nums) {
        while (expected < num) {
            missing.push_back(expected);
            expected++;
        }
        if (expected == num) {
            expected++;
        }
    }
    while (expected <= nums.size()) {
        missing.push_back(expected);
        expected++;
    }
    return missing;
}

int main() {
    vector<int> nums = {4,3,2,7,8,2,3,1};
    vector<int> result = findDisappearedNumbers(nums);
    for (int num : result) cout << num << " "; // Output: 5 6
    cout << endl;
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort the vector to find missing numbers by checking gaps.

vector<int> missing;Initialize vector to store missing numbers.

int expected = 1;Start expected number from 1.

for (int num : nums)Traverse sorted numbers to detect missing numbers.

while (expected < num)Add all missing numbers between expected and current number.

missing.push_back(expected);Add missing number to the result vector.

expected++;Increment expected number.

if (expected == num)If current number matches expected, move expected forward.

while (expected <= nums.size())Add any missing numbers after the last element.

return missing;Return the vector of missing numbers.

function findDisappearedNumbers(nums) {
    nums.sort((a,b) => a - b);
    const missing = [];
    let expected = 1;
    for (const num of nums) {
        while (expected < num) {
            missing.push(expected);
            expected++;
        }
        if (expected === num) {
            expected++;
        }
    }
    while (expected <= nums.length) {
        missing.push(expected);
        expected++;
    }
    return missing;
}

// Test
console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // Output: [5,6]

Line Notes

nums.sort((a,b) => a - b);Sort the array numerically to detect missing numbers by gaps.

const missing = [];Initialize array to collect missing numbers.

let expected = 1;Start expected number from 1.

for (const num of nums)Traverse sorted array to find missing numbers.

while (expected < num)Add all missing numbers between expected and current number.

missing.push(expected);Add missing number to the result array.

expected++;Increment expected number.

if (expected === num)If current number matches expected, move expected forward.

while (expected <= nums.length)Add any missing numbers after the last element.

return missing;Return the array of missing numbers.

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting takes O(n log n) time, scanning is O(n). Space depends on sorting algorithm used.

💡 For n=100,000, sorting is about 1.5 million operations, which is slower than linear but still acceptable.

Interview Verdict: Accepted but slower than optimal

Sorting is a common fallback but not the best for this problem; better in-place methods exist.

🧠

Optimal Cyclic Sort In-Place

💡 This approach uses the cyclic sort pattern to place each number at its correct index, enabling identification of missing numbers without extra space.

Intuition

Since numbers are from 1 to n, each number should be at index number-1. By swapping numbers to their correct positions, misplaced indices reveal missing numbers.

Algorithm

1. Initialize index i to 0.
2. While i < n, if nums[i] is not at its correct position and the target position does not already have the correct number, swap nums[i] with nums[nums[i]-1].
3. Else, increment i.
4. After sorting, traverse the array to collect indices where nums[i] != i + 1; these indices + 1 are missing numbers.
5. Return the collected missing numbers.

💡 This algorithm rearranges the array in-place to reveal missing numbers by mismatches, avoiding extra space.

</>

Code

def findDisappearedNumbers(nums):
    i = 0
    n = len(nums)
    while i < n:
        correct = nums[i] - 1
        if nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    missing = []
    for i in range(n):
        if nums[i] != i + 1:
            missing.append(i + 1)
    return missing

# Driver code
if __name__ == '__main__':
    print(findDisappearedNumbers([4,3,2,7,8,2,3,1]))  # Output: [5,6]

Line Notes

i = 0Start index at 0 to begin cyclic sort.

n = len(nums)Store length for loop bounds.

while i < n:Loop through array to place numbers correctly.

correct = nums[i] - 1Calculate correct index for current number.

if nums[i] != nums[correct]:Check if current number is misplaced and target position is different.

nums[i], nums[correct] = nums[correct], nums[i]Swap to place number at correct index.

else:If number is at correct position or duplicate, move forward.

i += 1Increment index to continue scanning.

missing = []Prepare list to collect missing numbers.

for i in range(n):Traverse array to find mismatches.

if nums[i] != i + 1:Mismatch indicates missing number at this index.

missing.append(i + 1)Add missing number to result.

import java.util.*;
public class Solution {
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        int i = 0, n = nums.length;
        while (i < n) {
            int correct = nums[i] - 1;
            if (nums[i] != nums[correct]) {
                int temp = nums[i];
                nums[i] = nums[correct];
                nums[correct] = temp;
            } else {
                i++;
            }
        }
        List<Integer> missing = new ArrayList<>();
        for (i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                missing.add(i + 1);
            }
        }
        return missing;
    }

    public static void main(String[] args) {
        System.out.println(findDisappearedNumbers(new int[]{4,3,2,7,8,2,3,1})); // Output: [5, 6]
    }
}

Line Notes

int i = 0, n = nums.length;Initialize index and store array length.

while (i < n)Loop to place numbers at correct indices.

int correct = nums[i] - 1;Calculate correct index for current number.

if (nums[i] != nums[correct])Check if current number is misplaced and target position differs.

int temp = nums[i]; nums[i] = nums[correct]; nums[correct] = temp;Swap numbers to correct position.

else { i++; }If number is correct or duplicate, move to next index.

List<Integer> missing = new ArrayList<>();Prepare list to collect missing numbers.

for (i = 0; i < n; i++)Traverse array to find mismatches.

if (nums[i] != i + 1)Mismatch indicates missing number.

missing.add(i + 1);Add missing number to result list.

#include <iostream>
#include <vector>
using namespace std;

vector<int> findDisappearedNumbers(vector<int>& nums) {
    int i = 0, n = nums.size();
    while (i < n) {
        int correct = nums[i] - 1;
        if (nums[i] != nums[correct]) {
            swap(nums[i], nums[correct]);
        } else {
            i++;
        }
    }
    vector<int> missing;
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            missing.push_back(i + 1);
        }
    }
    return missing;
}

int main() {
    vector<int> nums = {4,3,2,7,8,2,3,1};
    vector<int> result = findDisappearedNumbers(nums);
    for (int num : result) cout << num << " "; // Output: 5 6
    cout << endl;
    return 0;
}

Line Notes

int i = 0, n = nums.size();Initialize index and store vector size.

while (i < n)Loop to place numbers at correct indices.

int correct = nums[i] - 1;Calculate correct index for current number.

if (nums[i] != nums[correct])Check if current number is misplaced and target differs.

swap(nums[i], nums[correct]);Swap numbers to correct positions.

else { i++; }If number is correct or duplicate, move forward.

vector<int> missing;Prepare vector to collect missing numbers.

for (int i = 0; i < n; i++)Traverse vector to find mismatches.

if (nums[i] != i + 1)Mismatch indicates missing number.

missing.push_back(i + 1);Add missing number to result vector.

function findDisappearedNumbers(nums) {
    let i = 0, n = nums.length;
    while (i < n) {
        let correct = nums[i] - 1;
        if (nums[i] !== nums[correct]) {
            [nums[i], nums[correct]] = [nums[correct], nums[i]];
        } else {
            i++;
        }
    }
    const missing = [];
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            missing.push(i + 1);
        }
    }
    return missing;
}

// Test
console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // Output: [5,6]

Line Notes

let i = 0, n = nums.length;Initialize index and store array length.

while (i < n)Loop to place numbers at correct indices.

let correct = nums[i] - 1;Calculate correct index for current number.

if (nums[i] !== nums[correct])Check if current number is misplaced and target differs.

[nums[i], nums[correct]] = [nums[correct], nums[i]];Swap numbers to correct positions.

else { i++; }If number is correct or duplicate, move forward.

const missing = [];Initialize array to collect missing numbers.

for (let i = 0; i < n; i++)Traverse array to find mismatches.

if (nums[i] !== i + 1)Mismatch indicates missing number.

missing.push(i + 1);Add missing number to result array.

⏱

Complexity

TimeO(n)

SpaceO(1)

Each number is swapped at most once to its correct position, so total operations are linear. No extra space is used except output.

💡 For n=100,000, this means roughly 100,000 operations, which is very efficient.

Interview Verdict: Accepted and optimal

This is the best approach for this problem, combining efficiency and minimal space.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the optimal cyclic sort approach is preferred for its linear time and constant space. Brute force is good to mention for clarity, sorting is a fallback if unsure.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	Yes	Mention only - never code
2. Sorting and Linear Scan	O(n log n)	O(1) or O(n)	No	Yes	Mention as fallback, avoid coding if optimal known
3. Optimal Cyclic Sort In-Place	O(n)	O(1)	No	Yes	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach, and progressively optimize. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem constraints and input/output format.Step 2: Describe the brute force approach using extra space to track presence.Step 3: Discuss sorting and scanning for missing numbers.Step 4: Present the optimal cyclic sort approach and explain why it works.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Coding: 10min → Testing & edge cases: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to identify missing elements efficiently, optimize space usage, and implement cyclic sort correctly.

Common Follow-ups

• What if numbers are not in the range 1 to n? → Use hashing or sorting.
• Can you solve it without modifying the input array? → Use extra space or bit manipulation.

💡 These follow-ups test your adaptability and understanding of constraints beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Input array contains numbers in range 1 to n; 2) Need to find missing or duplicate numbers; 3) Problem hints at in-place rearrangement; 4) Constraints allow O(n) time and O(1) space.

Signature Phrases

numbers in the range 1 to nfind all missing numbersin-place rearrangement

NOT This Pattern When

Problems involving arbitrary numbers without range constraints or requiring subsequence computations are not cyclic sort.

Similar Problems

Find the Duplicate Number - uses cyclic sort to find duplicatesFirst Missing Positive - similar in-place rearrangement to find smallest missing positive

Practice

1. You are given an unsorted array of integers that may contain duplicates, negatives, and zeros. Your task is to find the smallest continuous range of positive integers that are missing from the array. Which algorithmic approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Using a hash set to store all positive numbers and then checking for the missing range

B. Sorting the array and then scanning linearly to find the missing range

C. Using a dynamic programming approach to track presence of numbers

D. Using cyclic sort to place each positive integer at its correct index and then scanning for the missing range

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the smallest missing positive range in O(n) time and O(1) space, which excludes sorting (O(n log n)) and hash sets (O(n) space).

2. Step 2: Identify the algorithm that achieves in-place linear time

   Cyclic sort places each positive integer at its correct index in the array, enabling a single pass to find the missing range efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cyclic sort is known for in-place linear time sorting of numbers in range 1 to n [OK]

Hint: Cyclic sort achieves O(n) time and O(1) space for this problem [OK]

Common Mistakes:

• Assuming sorting is optimal
• Confusing hash set space with time complexity

2. Identify the bug in the following cyclic sort implementation for finding the corrupt pair:

medium

A. Line 6: Missing increment of i after else condition

B. Line 3: Incorrect initialization of n

C. Line 7: Swap logic is incorrect

D. Line 10: Return statement does not handle all cases

Solution

1. Step 1: Analyze the while loop behavior

   Without incrementing i in the else branch, the loop can get stuck when nums[i] == nums[correct_index], causing infinite loop.

2. Step 2: Identify fix

   Adding i += 1 in the else branch ensures progress and termination.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Infinite loop caused by missing index increment [OK]

Hint: Always increment index if no swap to avoid infinite loops [OK]

Common Mistakes:

• Forgetting to increment index after no swap
• Swapping incorrectly
• Misplaced return statements

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. If the problem is changed so that numbers can appear multiple times (duplicates can appear more than twice), which modification to the cyclic sort approach is necessary to correctly find any duplicate?

hard

A. Use Floyd's Tortoise and Hare algorithm instead because cyclic sort fails with multiple duplicates

B. No modification needed; the current cyclic sort approach works for multiple duplicates

C. Modify the code to continue scanning after finding the first duplicate to find all duplicates

D. Add a hash set to track visited numbers since cyclic sort assumes only one duplicate

Solution

1. Step 1: Understand cyclic sort assumption

   Cyclic sort assumes exactly one duplicate; multiple duplicates break the unique mapping to indices.

2. Step 2: Identify solution for multiple duplicates

   Using a hash set tracks seen numbers and detects any duplicate regardless of count.

3. Step 3: Why other options fail

   Continuing cyclic sort won't find all duplicates; Floyd's algorithm detects one cycle only; no modification fails on multiple duplicates.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Hash set handles multiple duplicates correctly [OK]

Hint: Cyclic sort assumes one duplicate; hash set needed for multiple [OK]

Common Mistakes:

• Assuming cyclic sort works unchanged for multiple duplicates
• Thinking Floyd's algorithm finds all duplicates
• Trying to modify cyclic sort without extra space

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