Find Duplicate and Missing (Two Issues)

🎯

Find Duplicate and Missing (Two Issues)

mediumCYCLIC_SORTGoogleAmazon

Imagine a warehouse inventory system where each item should have a unique ID from 1 to n, but due to a scanning error, one ID is duplicated and another is missing. You need to quickly identify both the duplicate and the missing IDs to fix the records.

💡 This problem is about detecting two anomalies in a sequence: one number appears twice, and one number is missing. Beginners often struggle because it combines two issues in one array and requires careful handling to find both efficiently without extra space.

📋

Problem Statement

Given an array nums of size n containing numbers from 1 to n, exactly one number is duplicated and one number is missing. Find the duplicate number and the missing number and return them as a pair [duplicate, missing].

1 ≤ n ≤ 10^5nums.length == n1 ≤ nums[i] ≤ nExactly one number is duplicated and exactly one number is missing

💡

Example

Input"[3, 1, 2, 5, 3]"

Output[3, 4]

3 appears twice, and 4 is missing from the array.

Input"[1, 2, 2, 4]"

Output[2, 3]

2 is duplicated, and 3 is missing.

• Array of size 2, e.g. [2, 2] → duplicate=2, missing=1
• Duplicate is the first number, e.g. [1, 1, 3]
• Duplicate is the last number, e.g. [1, 2, 3, 4, 4]
• Missing number is 1, e.g. [2, 2, 3, 4]

⚠️

Common Mistakes

Not handling the case when missing number is at the end

Returns incorrect missing number

✅ Check if last element is less than n, if so missing = n

Swapping without checking if nums[i] == nums[correct_index]

Infinite loop or incorrect swaps

✅ Add condition to skip swap if numbers are equal

Using sorting approach but forgetting to initialize missing to 1

Misses missing number if it's 1

✅ Initialize missing to 1 before loop

Brute force approach is too slow and causes TLE on large inputs

Timeout in interviews or tests

✅ Mention brute force only, then optimize to sorting or cyclic sort

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by checking every pair and counting occurrences, even though it's inefficient. It builds intuition about what we are looking for.

Intuition

Check each number from 1 to n and count how many times it appears in the array. The one that appears twice is the duplicate, and the one that appears zero times is missing.

Algorithm

1. For each number from 1 to n, count its occurrences in the array.
2. If count is 2, record it as the duplicate.
3. If count is 0, record it as the missing number.
4. Return the pair [duplicate, missing].

💡 This approach is straightforward but inefficient because it repeatedly scans the array for each number, which is easy to understand but slow.

</>

Code

def find_duplicate_missing(nums):
    n = len(nums)
    duplicate = -1
    missing = -1
    for num in range(1, n + 1):
        count = 0
        for x in nums:
            if x == num:
                count += 1
        if count == 2:
            duplicate = num
        elif count == 0:
            missing = num
    return [duplicate, missing]

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

Line Notes

for num in range(1, n + 1):Iterate over all possible numbers to check their frequency

count = 0Initialize count for current number

for x in nums:Scan entire array to count occurrences of num

if count == 2:Identify the duplicate number

elif count == 0:Identify the missing number

return [duplicate, missing]Return the final answer as a pair

import java.util.*;
public class Solution {
    public static int[] findDuplicateMissing(int[] nums) {
        int n = nums.length;
        int duplicate = -1, missing = -1;
        for (int num = 1; num <= n; num++) {
            int count = 0;
            for (int x : nums) {
                if (x == num) count++;
            }
            if (count == 2) duplicate = num;
            else if (count == 0) missing = num;
        }
        return new int[]{duplicate, missing};
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 5, 3};
        int[] res = findDuplicateMissing(nums);
        System.out.println(Arrays.toString(res)); // [3, 4]
    }
}

Line Notes

for (int num = 1; num <= n; num++) {Loop over all numbers to check frequency

int count = 0;Reset count for each number

for (int x : nums) {Count occurrences of num in array

if (count == 2) duplicate = num;Mark duplicate when count is 2

else if (count == 0) missing = num;Mark missing when count is 0

return new int[]{duplicate, missing};Return result as array

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

vector<int> findDuplicateMissing(vector<int>& nums) {
    int n = nums.size();
    int duplicate = -1, missing = -1;
    for (int num = 1; num <= n; num++) {
        int count = 0;
        for (int x : nums) {
            if (x == num) count++;
        }
        if (count == 2) duplicate = num;
        else if (count == 0) missing = num;
    }
    return {duplicate, missing};
}

int main() {
    vector<int> nums = {3, 1, 2, 5, 3};
    vector<int> res = findDuplicateMissing(nums);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // [3, 4]
    return 0;
}

Line Notes

for (int num = 1; num <= n; num++) {Check each number from 1 to n

int count = 0;Initialize count for current number

for (int x : nums) {Count occurrences of num in array

if (count == 2) duplicate = num;Identify duplicate number

else if (count == 0) missing = num;Identify missing number

return {duplicate, missing};Return the pair as vector

function findDuplicateMissing(nums) {
    const n = nums.length;
    let duplicate = -1, missing = -1;
    for (let num = 1; num <= n; num++) {
        let count = 0;
        for (const x of nums) {
            if (x === num) count++;
        }
        if (count === 2) duplicate = num;
        else if (count === 0) missing = num;
    }
    return [duplicate, missing];
}

// Test
console.log(findDuplicateMissing([3, 1, 2, 5, 3])); // [3, 4]

Line Notes

for (let num = 1; num <= n; num++) {Iterate over all possible numbers

let count = 0;Reset count for each number

for (const x of nums) {Count occurrences of num in array

if (count === 2) duplicate = num;Detect duplicate number

else if (count === 0) missing = num;Detect missing number

return [duplicate, missing];Return the final result

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each number from 1 to n, we scan the entire array of size n to count occurrences, resulting in O(n*n) = O(n^2) time. Space is constant as no extra data structures are used.

💡 If n=1000, this means about 1,000,000 operations, which is slow and impractical for large inputs.

Interview Verdict: Use only to introduce - too slow for large inputs

This approach is too slow for big arrays but helps understand the problem and correctness before optimizing.

🧠

Sorting Based Approach

💡 Sorting the array puts numbers in order, making it easier to spot duplicates and missing numbers by comparing neighbors. This is a common intermediate step before the optimal in-place approach.

Intuition

Sort the array, then scan it once to find where the current number equals the previous (duplicate) and where the sequence breaks (missing).

Algorithm

1. Sort the array in ascending order.
2. Initialize variables for duplicate and missing.
3. Traverse the sorted array and compare each element with the previous one.
4. If two adjacent elements are equal, record the duplicate.
5. If the difference between adjacent elements is more than 1, record the missing number as previous + 1.
6. Check for missing number at the boundaries (start or end).
7. Return [duplicate, missing].

💡 Sorting makes anomalies appear as adjacent duplicates or gaps, which are easy to detect in one pass.

</>

Code

def find_duplicate_missing(nums):
    nums.sort()
    duplicate = -1
    missing = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            duplicate = nums[i]
        elif nums[i] > nums[i - 1] + 1:
            missing = nums[i - 1] + 1
    if nums[-1] < len(nums):
        missing = len(nums)
    return [duplicate, missing]

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

Line Notes

nums.sort()Sort array to bring duplicates and gaps together

duplicate = -1Initialize duplicate placeholder

missing = 1Initialize missing to 1, covers missing at start

for i in range(1, len(nums))Traverse array from second element

if nums[i] == nums[i - 1]Detect duplicate by equality

elif nums[i] > nums[i - 1] + 1Detect missing number by gap

if nums[-1] < len(nums)Check if missing number is at the end (less than n)

return [duplicate, missing]Return the result

import java.util.*;
public class Solution {
    public static int[] findDuplicateMissing(int[] nums) {
        Arrays.sort(nums);
        int duplicate = -1, missing = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) duplicate = nums[i];
            else if (nums[i] > nums[i - 1] + 1) missing = nums[i - 1] + 1;
        }
        if (nums[nums.length - 1] < nums.length) missing = nums.length;
        return new int[]{duplicate, missing};
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 5, 3};
        int[] res = findDuplicateMissing(nums);
        System.out.println(Arrays.toString(res)); // [3, 4]
    }
}

Line Notes

Arrays.sort(nums);Sort array to detect anomalies easily

int duplicate = -1, missing = 1;Initialize variables for results

for (int i = 1; i < nums.length; i++) {Traverse sorted array

if (nums[i] == nums[i - 1]) duplicate = nums[i];Detect duplicate

else if (nums[i] > nums[i - 1] + 1) missing = nums[i - 1] + 1;Detect missing number

if (nums[nums.length - 1] < nums.length) missing = nums.length;Check missing at end (less than n)

return new int[]{duplicate, missing};Return result

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

vector<int> findDuplicateMissing(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int duplicate = -1, missing = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] == nums[i - 1]) duplicate = nums[i];
        else if (nums[i] > nums[i - 1] + 1) missing = nums[i - 1] + 1;
    }
    if (nums.back() < nums.size()) missing = nums.size();
    return {duplicate, missing};
}

int main() {
    vector<int> nums = {3, 1, 2, 5, 3};
    vector<int> res = findDuplicateMissing(nums);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // [3, 4]
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array to detect duplicates and gaps

int duplicate = -1, missing = 1;Initialize variables

for (int i = 1; i < nums.size(); i++) {Traverse sorted array

if (nums[i] == nums[i - 1]) duplicate = nums[i];Detect duplicate

else if (nums[i] > nums[i - 1] + 1) missing = nums[i - 1] + 1;Detect missing number

if (nums.back() < nums.size()) missing = nums.size();Check missing at end (less than n)

return {duplicate, missing};Return result

function findDuplicateMissing(nums) {
    nums.sort((a, b) => a - b);
    let duplicate = -1, missing = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) duplicate = nums[i];
        else if (nums[i] > nums[i - 1] + 1) missing = nums[i - 1] + 1;
    }
    if (nums[nums.length - 1] < nums.length) missing = nums.length;
    return [duplicate, missing];
}

// Test
console.log(findDuplicateMissing([3, 1, 2, 5, 3])); // [3, 4]

Line Notes

nums.sort((a, b) => a - b);Sort array numerically

let duplicate = -1, missing = 1;Initialize variables

for (let i = 1; i < nums.length; i++) {Traverse sorted array

if (nums[i] === nums[i - 1]) duplicate = nums[i];Detect duplicate

else if (nums[i] > nums[i - 1] + 1) missing = nums[i - 1] + 1;Detect missing number

if (nums[nums.length - 1] < nums.length) missing = nums.length;Check missing at end (less than n)

return [duplicate, missing];Return result

⏱

Complexity

TimeO(n log n)

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

Sorting takes O(n log n) time, then a single pass O(n) to find anomalies. Space depends on sorting algorithm but can be O(1) for in-place sorts.

💡 For n=1000, sorting takes about 10,000 operations, much faster than brute force.

Interview Verdict: Accepted but not optimal

This approach is acceptable in interviews if you mention the optimal in-place method afterwards.

🧠

Optimal Cyclic Sort Approach

💡 Cyclic sort leverages the fact that numbers are from 1 to n and places each number at its correct index. This approach finds the duplicate and missing in one pass without extra space.

Intuition

Place each number at its correct index (num-1). If a number is already at the correct index, it must be a duplicate. After placement, the index where the number is incorrect indicates the missing number.

Algorithm

1. Initialize index i = 0.
2. While i < n, if nums[i] != i + 1 and nums[i] != nums[nums[i] - 1], swap nums[i] with nums[nums[i] - 1].
3. Else, increment i.
4. After sorting, traverse the array to find the index where nums[i] != i + 1.
5. The number at that index is the duplicate, and i + 1 is the missing number.
6. Return [duplicate, missing].

💡 The cyclic sort places numbers in correct positions, revealing the duplicate and missing by mismatch.

</>

Code

def find_duplicate_missing(nums):
    i = 0
    n = len(nums)
    while i < n:
        correct_index = nums[i] - 1
        if nums[i] != nums[correct_index]:
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return [nums[i], i + 1]
    return [-1, -1]

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

Line Notes

i = 0Start index for cyclic sort

correct_index = nums[i] - 1Calculate correct position for current number

if nums[i] != nums[correct_index]:Check if current number is at correct position or duplicate

nums[i], nums[correct_index] = nums[correct_index], nums[i]Swap to place number correctly

else:If no swap needed, move to next index

i += 1Increment index when no swap

for i in range(n):After sorting, find mismatch

if nums[i] != i + 1:Mismatch indicates duplicate and missing

return [nums[i], i + 1]Return duplicate and missing

public class Solution {
    public static int[] findDuplicateMissing(int[] nums) {
        int i = 0, n = nums.length;
        while (i < n) {
            int correctIndex = nums[i] - 1;
            if (nums[i] != nums[correctIndex]) {
                int temp = nums[i];
                nums[i] = nums[correctIndex];
                nums[correctIndex] = temp;
            } else {
                i++;
            }
        }
        for (i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return new int[]{nums[i], i + 1};
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 5, 3};
        int[] res = findDuplicateMissing(nums);
        System.out.println(java.util.Arrays.toString(res)); // [3, 4]
    }
}

Line Notes

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

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

if (nums[i] != nums[correctIndex]) {Check if swap needed

swap nums[i] and nums[correctIndex]Place number at correct index

else {If no swap needed, move to next index

i++;Increment index when no swap

for (i = 0; i < n; i++) {Find mismatch after sorting

if (nums[i] != i + 1)Mismatch indicates duplicate and missing

return new int[]{nums[i], i + 1};Return result

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

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

int main() {
    vector<int> nums = {3, 1, 2, 5, 3};
    vector<int> res = findDuplicateMissing(nums);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // [3, 4]
    return 0;
}

Line Notes

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

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

if (nums[i] != nums[correctIndex]) {Check if swap needed

swap(nums[i], nums[correctIndex]);Place number at correct index

else {If no swap needed, move to next index

i++;Increment index when no swap

for (int i = 0; i < n; i++) {Find mismatch after sorting

if (nums[i] != i + 1)Mismatch indicates duplicate and missing

return {nums[i], i + 1};Return result

function findDuplicateMissing(nums) {
    let i = 0, n = nums.length;
    while (i < n) {
        let correctIndex = nums[i] - 1;
        if (nums[i] !== nums[correctIndex]) {
            [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return [nums[i], i + 1];
        }
    }
    return [-1, -1];
}

// Test
console.log(findDuplicateMissing([3, 1, 2, 5, 3])); // [3, 4]

Line Notes

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

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

if (nums[i] !== nums[correctIndex]) {Check if swap needed

[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];Swap to place number correctly

else {If no swap needed, move to next index

i++;Increment index when no swap

for (let i = 0; i < n; i++) {Find mismatch after sorting

if (nums[i] !== i + 1)Mismatch indicates duplicate and missing

return [nums[i], i + 1];Return result

⏱

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 besides variables.

💡 For n=1000, this means roughly 1000 operations, very efficient for large inputs.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the cyclic sort approach in 95% of interviews for this problem because it is optimal in time and space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	Yes	Mention only - never code
2. Sorting Based	O(n log n)	O(1) or O(log n)	No	Yes	Acceptable if followed by optimal approach
3. Optimal Cyclic Sort	O(n)	O(1)	No	Yes	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know how to present your solution clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Discuss sorting approach as an improvement.Step 4: Present the optimal cyclic sort approach with code.Step 5: Test your code with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewers test your problem understanding, ability to optimize, code correctness, and handling of edge cases.

Common Follow-ups

• What if there are multiple duplicates and missing numbers? → Use hash maps or extended cyclic sort.
• Can you solve it without modifying the input array? → Use extra space or mathematical formulas.

💡 These follow-ups test your ability to adapt solutions to variations and constraints.

🔍

Pattern Recognition

When to Use

1) Array contains numbers from 1 to n; 2) Exactly one duplicate and one missing number; 3) Need to find both anomalies; 4) Constraints allow in-place modification.

Signature Phrases

'array of size n containing numbers from 1 to n''exactly one number is duplicated and one is missing'

NOT This Pattern When

Problems with multiple duplicates/missing or arbitrary ranges require different approaches.

Similar Problems

Find All Duplicates in an Array - similar cyclic sort technique to find duplicatesFind All Missing Numbers - similar approach to find missing numbers

Practice

1. You are given an array of size n containing numbers from 1 to n with exactly one number duplicated and one number missing. Which algorithmic approach guarantees finding both the duplicate and missing numbers in O(n) time and O(1) extra space?

easy

A. Using cyclic sort to place each number at its correct index and then scanning for mismatch

B. Sorting the array and then scanning for the duplicate and missing numbers

C. Using a dynamic programming approach to track counts of each number

D. Using a greedy approach to pick numbers and mark visited elements

Solution

1. Step 1: Understand problem constraints

   The array has numbers from 1 to n with one duplicate and one missing number, so placing each number at its correct index reveals the corrupt pair.

2. Step 2: Identify the best approach

   Cyclic sort places each number at index = number - 1 in O(n) time and O(1) space, enabling detection of the mismatch directly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cyclic sort is optimal for this problem pattern [OK]

Hint: Cyclic sort fits missing+duplicate in O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming sorting is always optimal
• Confusing DP with counting
• Using greedy without index placement

2. Consider the following code snippet implementing the optimal approach for finding the first missing positive integer. What is the output when the input is [3, 4, -1, 1]?

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Trace the cyclic sort swaps

   Initial array: [3,4,-1,1] - i=0: nums[0]=3, swap nums[2] and nums[0] -> [-1,4,3,1] - i=0 again: nums[0]=-1 (out of range), move on - i=1: nums[1]=4, swap nums[3] and nums[1] -> [-1,1,3,4] - i=1 again: nums[1]=1, swap nums[0] and nums[1] -> [1,-1,3,4] - i=1 again: nums[1]=-1 (out of range), move on - i=2 and i=3 no swaps needed

2. Step 2: Scan for first missing positive

   Array after rearrangement: [1,-1,3,4] Check indices: - i=0: nums[0]=1 (correct) - i=1: nums[1]=-1 (incorrect), so return i+1=2

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected missing positive 2 [OK]

Hint: After cyclic sort, first mismatch index + 1 is missing positive [OK]

Common Mistakes:

• Off-by-one errors in return value
• Not handling negative or out-of-range values
• Infinite loops due to missing swap condition

3. What is the time complexity of the cyclic sort approach to find the missing number in an array of size n, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because each number is swapped at most once to its correct position

B. O(n log n) because of the swaps resembling sorting

C. O(n^2) because nested loops are implied by the swapping inside the while loop

D. O(n) but with O(n) auxiliary space due to recursion stack

Solution

1. Step 1: Identify loop behavior

   The while loop swaps numbers to their correct indices. Each number can be swapped at most once before it is in place.

2. Step 2: Analyze total operations

   Since each swap places a number correctly, total swaps ≤ n, so total time is O(n). No nested full loops occur.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time due to limited swaps and single pass [OK]

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

Common Mistakes:

• Assuming swaps cause nested loops and O(n^2) time
• Confusing with sorting algorithms that are O(n log n)
• Thinking recursion adds extra space

4. Suppose the problem changes: the array can contain duplicates and you want to find the first missing positive integer that is NOT present, but numbers can be reused multiple times in the array. Which modification to the optimal cyclic sort approach correctly handles this?

hard

A. Sort the array first and then scan linearly to handle duplicates properly

B. Use the same cyclic sort approach without changes; duplicates do not affect correctness

C. Modify the while loop to skip swapping if the target index already contains the same number to avoid infinite loops

D. Use a hash set to track seen numbers and then find the missing positive

Solution

1. Step 1: Understand the impact of duplicates

   Duplicates cause infinite swapping if the code swaps without checking if the target position already has the same number.

2. Step 2: Modify the swap condition

   Adding a check to skip swapping when nums[nums[i]-1] == nums[i] prevents infinite loops and correctly places unique numbers.

3. Step 3: Evaluate other options

   Sorting or hash sets increase time or space complexity, and naive cyclic sort fails with duplicates.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Proper swap condition handles duplicates without extra space [OK]

Hint: Skip swaps if target index already has the same number [OK]

Common Mistakes:

• Ignoring duplicates causing infinite loops
• Switching to sorting losing O(n) time
• Using extra space unnecessarily

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