Find the Corrupt Pair (Custom Variant)

🎯

Find the Corrupt Pair (Custom Variant)

easyCYCLIC_SORTAmazon

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 find both the duplicate and the missing IDs to fix the records.

💡 This problem involves identifying a pair of numbers where one number is duplicated and another is missing in a sequence. Beginners often struggle because the problem requires careful indexing and understanding how to detect anomalies in a nearly sorted array without extra space.

📋

Problem Statement

Given an array 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^5Array elements are integers in the range [1, n]Exactly one number is duplicated and exactly one number is missing

💡

Example

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

Output[3, 4]

3 is duplicated and 4 is missing from the sequence 1 to 5.

• Array with minimum size n=2, e.g. [2, 2] → duplicate=2, missing=1
• Duplicate is the last number, e.g. [1, 2, 3, 4, 4] → duplicate=4, missing=5
• Duplicate is the first number, e.g. [1, 1, 3, 4, 5] → duplicate=1, missing=2
• Array where missing number is in the middle, e.g. [1, 2, 2, 4, 5] → duplicate=2, missing=3

⚠️

Common Mistakes

Not handling the case when the missing number is the last number

Returns incorrect missing number or misses it entirely

✅ Add explicit check after traversal to verify if last number is missing

Infinite loop in cyclic sort due to not incrementing index after swap

Code runs indefinitely or crashes

✅ Only increment index when no swap occurs to ensure progress

Using sorting but forgetting to handle duplicates properly

Duplicate or missing number not detected correctly

✅ Check both duplicate and missing conditions carefully during linear scan

Off-by-one errors when indexing frequency array or cyclic sort

Wrong duplicate or missing number returned

✅ Remember to adjust indices by subtracting or adding 1 appropriately

🧠

Brute Force (Sorting + Linear Scan)

💡 This approach is straightforward and helps beginners understand the problem by sorting the array and then scanning for anomalies. It is not optimal but builds intuition about the problem structure.

Intuition

Sort the array so that numbers should ideally be in order from 1 to n. Then scan through to find where the order breaks: the duplicate will appear twice consecutively, and the missing number is the one that should have appeared but didn't.

Algorithm

1. Sort the input array.
2. Initialize variables to store duplicate and missing numbers.
3. Traverse the sorted array and check for consecutive duplicates.
4. Identify the missing number by comparing expected and actual values.

💡 Sorting makes the problem easier to visualize but costs extra time. The linear scan after sorting is simple but requires careful checks to find both duplicate and missing numbers.

</>

Code

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

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

Line Notes

nums.sort()Sorting the array to bring duplicates next to each other

duplicate = -1Initialize duplicate to an invalid value to detect later

missing = -1Initialize missing to invalid value to detect later

for i in range(len(nums) - 1)Traverse array to compare adjacent elements

if nums[i] == nums[i + 1]Detect duplicate when two adjacent elements are equal

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

if missing == -1If missing not found in loop, check edge cases

if nums[-1] != len(nums)Check if last number is missing (edge case)

else: missing = 1If last number is correct and missing not found, missing is 1

return [duplicate, missing]Return the found duplicate and missing numbers

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

    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 5, 3};
        int[] result = findCorruptPair(arr);
        System.out.println(Arrays.toString(result)); // Output: [3, 4]
    }
}

Line Notes

Arrays.sort(nums);Sort array to bring duplicates together

int duplicate = -1;Initialize duplicate to invalid value

int missing = -1;Initialize missing to invalid value

for (int i = 0; i < nums.length - 1; i++)Loop to check adjacent elements

if (nums[i] == nums[i + 1])Detect duplicate by equality of neighbors

else if (nums[i + 1] > nums[i] + 1)Detect missing number by gap

if (missing == -1)If missing not found in loop, check edge cases

if (nums[nums.length - 1] != nums.length)Check if last number is missing

else { missing = 1; }If last number correct and missing not found, missing is 1

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

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    vector<int> arr = {3, 1, 2, 5, 3};
    vector<int> res = findCorruptPair(arr);
    cout << "[" << res[0] << ", " << res[1] << "]\n"; // Output: [3, 4]
    return 0;
}

Line Notes

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

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

for (int i = 0; i < (int)nums.size() - 1; i++)Traverse array to find anomalies

if (nums[i] == nums[i + 1])Duplicate detected by equal adjacent elements

else if (nums[i + 1] > nums[i] + 1)Gap indicates missing number

if (missing == -1)If missing not found in loop, check edge cases

if (nums.back() != (int)nums.size())Check if last number is missing

else { missing = 1; }If last number correct and missing not found, missing is 1

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

cout << ...Print the result for verification

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

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

Line Notes

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

let duplicate = -1;Initialize duplicate to invalid value

let missing = -1;Initialize missing to invalid value

for (let i = 0; i < nums.length - 1; i++)Loop through array to find anomalies

if (nums[i] === nums[i + 1])Detect duplicate by equality

else if (nums[i + 1] > nums[i] + 1)Detect missing number by gap

if (missing === -1)If missing not found in loop, check edge cases

if (nums[nums.length - 1] !== nums.length)Check if last number is missing

else { missing = 1; }If last number correct and missing not found, missing is 1

return [duplicate, missing];Return the result pair

⏱

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). Sorting may use extra space depending on language.

💡 For n=100,000, sorting is feasible but not optimal; this approach is good for understanding but not best for large inputs.

Interview Verdict: Accepted but not optimal

This approach works but is slower than optimal solutions; good to mention but not preferred to code in interviews.

🧠

Better Approach (Frequency Array)

💡 Using a frequency array helps beginners understand how counting occurrences can identify duplicates and missing numbers without sorting.

Intuition

Create a frequency array of size n to count occurrences of each number. The number with frequency 2 is the duplicate, and the number with frequency 0 is missing.

Algorithm

1. Initialize a frequency array of size n with zeros.
2. Traverse the input array and increment frequency for each number.
3. Scan the frequency array to find the number with frequency 2 (duplicate) and frequency 0 (missing).
4. Return the duplicate and missing numbers.

💡 This approach uses extra space but is conceptually simpler and faster than sorting.

</>

Code

def find_corrupt_pair(nums):
    n = len(nums)
    freq = [0] * n
    for num in nums:
        freq[num - 1] += 1
    duplicate = -1
    missing = -1
    for i in range(n):
        if freq[i] == 2:
            duplicate = i + 1
        elif freq[i] == 0:
            missing = i + 1
    return [duplicate, missing]

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

Line Notes

freq = [0] * nInitialize frequency array to count occurrences

for num in nums:Traverse input to count each number

freq[num - 1] += 1Increment frequency for the number's index

duplicate = -1Initialize duplicate to invalid value

missing = -1Initialize missing to invalid value

for i in range(n):Scan frequency array to find anomalies

if freq[i] == 2:Duplicate number found by frequency 2

elif freq[i] == 0:Missing number found by frequency 0

return [duplicate, missing]Return the identified pair

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

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

Line Notes

int[] freq = new int[n];Create frequency array to count occurrences

for (int num : nums)Traverse input array to count numbers

freq[num - 1]++;Increment frequency for each number

int duplicate = -1, missing = -1;Initialize duplicate and missing to invalid values

for (int i = 0; i < n; i++)Scan frequency array for duplicate and missing

if (freq[i] == 2)Duplicate detected by frequency 2

else if (freq[i] == 0)Missing detected by frequency 0

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

#include <bits/stdc++.h>
using namespace std;

vector<int> findCorruptPair(vector<int>& nums) {
    int n = (int)nums.size();
    vector<int> freq(n, 0);
    for (int num : nums) {
        freq[num - 1]++;
    }
    int duplicate = -1, missing = -1;
    for (int i = 0; i < n; i++) {
        if (freq[i] == 2) duplicate = i + 1;
        else if (freq[i] == 0) missing = i + 1;
    }
    return {duplicate, missing};
}

int main() {
    vector<int> arr = {3, 1, 2, 5, 3};
    vector<int> res = findCorruptPair(arr);
    cout << "[" << res[0] << ", " << res[1] << "]\n"; // Output: [3, 4]
    return 0;
}

Line Notes

vector<int> freq(n, 0);Initialize frequency vector with zeros

for (int num : nums)Count occurrences of each number

freq[num - 1]++;Increment frequency for number's index

int duplicate = -1, missing = -1;Initialize duplicate and missing to invalid values

for (int i = 0; i < n; i++)Scan frequency array for anomalies

if (freq[i] == 2)Duplicate number found

else if (freq[i] == 0)Missing number found

return {duplicate, missing};Return the pair

cout << ...Print result for verification

function findCorruptPair(nums) {
    const n = nums.length;
    const freq = new Array(n).fill(0);
    for (const num of nums) {
        freq[num - 1]++;
    }
    let duplicate = -1, missing = -1;
    for (let i = 0; i < n; i++) {
        if (freq[i] === 2) duplicate = i + 1;
        else if (freq[i] === 0) missing = i + 1;
    }
    return [duplicate, missing];
}

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

Line Notes

const freq = new Array(n).fill(0);Create frequency array initialized to zero

for (const num of nums)Count each number's occurrence

freq[num - 1]++;Increment frequency for number's index

let duplicate = -1, missing = -1;Initialize duplicate and missing to invalid values

for (let i = 0; i < n; i++)Scan frequency array for duplicate and missing

if (freq[i] === 2)Duplicate detected by frequency 2

else if (freq[i] === 0)Missing detected by frequency 0

return [duplicate, missing];Return the result pair

⏱

Complexity

TimeO(n)

SpaceO(n)

Counting frequencies and scanning takes linear time and space proportional to input size.

💡 For n=100,000, this approach is faster than sorting but uses extra memory for frequency array.

Interview Verdict: Accepted and faster than sorting

This approach is a good improvement but uses extra space; it is often acceptable in interviews.

🧠

Optimal Approach (Cyclic Sort In-Place)

💡 This approach uses the cyclic sort pattern to place each number at its correct index, enabling detection of duplicate and missing numbers in O(n) time and O(1) space.

Intuition

Since numbers are from 1 to n, each number should be at index number-1. By swapping elements to their correct positions, the duplicate will cause a conflict, and the missing number will be the index where the correct number is not present.

Algorithm

1. Initialize index i to 0.
2. While i < n, if nums[i] is not at its correct position and not equal to the number at its target position, swap it with the number at its correct position.
3. Else, increment i.
4. After sorting, traverse the array to find the index where nums[i] != i + 1; that index + 1 is missing and nums[i] is duplicate.

💡 This approach rearranges the array in-place to reveal the corrupt pair without extra space or sorting overhead.

</>

Code

def find_corrupt_pair(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__':
    arr = [3, 1, 2, 5, 3]
    print(find_corrupt_pair(arr))  # Output: [3, 4]

Line Notes

i = 0Start index for traversal

n = len(nums)Store length of array

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 needs swapping

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

else: i += 1Increment index only if no swap needed to avoid infinite loop

for i in range(n)Traverse to find mismatch after sorting

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

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

public class Solution {
    public static int[] findCorruptPair(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[] arr = {3, 1, 2, 5, 3};
        int[] res = findCorruptPair(arr);
        System.out.println(java.util.Arrays.toString(res)); // Output: [3, 4]
    }
}

Line Notes

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

int correctIndex = nums[i] - 1;Calculate correct position for current element

if (nums[i] != nums[correctIndex])Check if swap needed to place element correctly

int temp = nums[i]; nums[i] = nums[correctIndex]; nums[correctIndex] = temp;Perform swap to correct position

else { i++; }Increment index only if no swap to avoid infinite loop

for (i = 0; i < n; i++)Scan array to find mismatch after sorting

if (nums[i] != i + 1)Mismatch indicates corrupt pair

return new int[]{nums[i], i + 1};Return duplicate and missing numbers

#include <bits/stdc++.h>
using namespace std;

vector<int> findCorruptPair(vector<int>& nums) {
    int i = 0, n = (int)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> arr = {3, 1, 2, 5, 3};
    vector<int> res = findCorruptPair(arr);
    cout << "[" << res[0] << ", " << res[1] << "]\n"; // Output: [3, 4]
    return 0;
}

Line Notes

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

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

if (nums[i] != nums[correctIndex])Check if current element is misplaced

swap(nums[i], nums[correctIndex]);Swap to place element correctly

else { i++; }Increment index only if no swap to avoid infinite loop

for (int i = 0; i < n; i++)Scan array to find mismatch after sorting

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

return {nums[i], i + 1};Return the corrupt pair

function findCorruptPair(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(findCorruptPair([3, 1, 2, 5, 3])); // Output: [3, 4]

Line Notes

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

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

if (nums[i] !== nums[correctIndex])Check if swap needed to place number correctly

[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];Swap elements in-place

else { i++; }Increment index only if no swap to avoid infinite loop

for (let i = 0; i < n; i++)Traverse array to find mismatch after sorting

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

return [nums[i], i + 1];Return the corrupt pair

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is swapped at most once to its correct position, so linear time. No extra space used except variables.

💡 For n=100,000, this approach is very efficient and uses minimal memory, ideal for interviews.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for this problem due to its efficiency and in-place operation.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the cyclic sort approach is preferred due to its optimal time and space. Frequency array is acceptable if extra space is allowed. Sorting is good for initial explanation but not ideal to code.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Sorting + Linear Scan)	O(n log n)	O(1) or O(n) depending on sort	No	Yes	Mention only - never code
2. Better (Frequency Array)	O(n)	O(n)	No	Yes	Good to mention, acceptable to code if space allowed
3. Optimal (Cyclic Sort In-Place)	O(n)	O(1)	No	Yes	Best approach to code in interviews

💼

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 improve to the optimal solution. 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 sorting and scanning.Step 3: Explain the frequency array method as a better approach.Step 4: Present the cyclic sort approach as the optimal solution.Step 5: Code the optimal approach and test with examples.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of array indexing, ability to optimize from naive to efficient solutions, and coding accuracy for in-place swaps.

Common Follow-ups

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

💡 These follow-ups test your ability to generalize the solution and handle constraints like read-only input.

🔍

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 corrupt pair; 4) In-place or O(n) time solution desired.

Signature Phrases

'exactly one number is duplicated and one number is missing''numbers from 1 to n with one corrupt pair'

NOT This Pattern When

Problems involving arbitrary duplicates without missing numbers or unsorted arrays without constraints are not cyclic sort.

Similar Problems

Find the Duplicate Number - focuses on finding duplicate onlySet Mismatch - similar problem with duplicate and missingFind All Duplicates in an Array - extension to multiple duplicates

Practice

1. Given the following code snippet, what is the output when the input array is [3,1,2,2]?

easy

A. []

B. [3]

C. [1]

D. [2]

Solution

1. Step 1: Trace swaps in while loop

   Initial array: [3,1,2,2]. Swap nums[0] and nums[2]: [2,1,3,2]. Swap nums[0] and nums[1]: [1,2,3,2]. i increments to 1,2,3 without swaps.

2. Step 2: Identify duplicates in final array

   Final array: [1,2,3,2]. Index 3 has value 2 instead of 4, so duplicate is 2.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only 2 appears twice, correctly identified [OK]

Hint: Trace swaps carefully to find duplicates [OK]

Common Mistakes:

• Confusing index and value during swaps
• Missing the duplicate in final scan
• Off-by-one errors in final check

2. You are given an unsorted array of integers that may contain duplicates and negative numbers. Your task is to find the first k positive integers missing from the array. Which algorithmic approach guarantees an optimal time complexity while handling duplicates and negatives correctly?

easy

A. Sort the array and then scan sequentially to find missing positive numbers.

B. Use dynamic programming to build a table of present and missing numbers.

C. Use cyclic sort to place numbers in their correct indices, then identify missing positives and track extras with a boolean array.

D. Use a max-heap to extract the smallest missing positive numbers one by one.

Solution

1. Step 1: Understand problem constraints

   The array may contain duplicates and negative numbers, so naive sorting or heap approaches may be inefficient or incorrect.

2. Step 2: Identify optimal approach

   Cyclic sort places numbers in their correct indices in O(n) time, ignoring negatives and duplicates. Then, a boolean array tracks extra numbers beyond the array length to find missing positives efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cyclic sort + boolean array handles duplicates and negatives optimally [OK]

Hint: Cyclic sort handles duplicates and negatives efficiently [OK]

Common Mistakes:

• Assuming sorting is always optimal
• Using heaps which add unnecessary overhead
• Confusing DP with presence tracking

3. What is the time complexity of the optimal cyclic sort approach for finding all missing numbers in an array of size n, and why?

medium

A. O(n log n) because of the sorting-like swaps

B. O(n^2) because nested swaps can occur repeatedly for duplicates

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

D. O(n) but with O(n) auxiliary space for tracking swaps

Solution

1. Step 1: Analyze the while loop behavior

   Each number is swapped at most once to its correct index, so total swaps ≤ n.

2. Step 2: Confirm no nested repeated swaps

   Duplicates cause skipping increments but do not cause repeated swaps for the same element, so total operations remain linear.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

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

Hint: Each element swaps at most once [OK]

Common Mistakes:

• Assuming sorting cost O(n log n)
• Thinking duplicates cause quadratic swaps
• Confusing auxiliary space with time

4. Suppose the input array can contain numbers from 1 to n but may have multiple duplicates and multiple missing numbers. Which of the following modifications to the cyclic sort approach correctly finds all duplicates and missing numbers efficiently?

hard

A. Modify the cyclic sort to swap only when nums[i] != nums[correct_index] and keep a separate hash set to track duplicates.

B. Run the cyclic sort as usual, then scan the array to collect all indices where nums[i] != i + 1, returning all duplicates and missing numbers.

C. Use the original cyclic sort approach repeatedly until no swaps occur, then identify duplicates and missing numbers.

D. Sort the array using built-in sort and then scan once to find all duplicates and missing numbers.

Solution

1. Step 1: Understand the problem extension

   Multiple duplicates and missing numbers require identifying all mismatches after cyclic sort.

2. Step 2: Modify cyclic sort approach

   Perform cyclic sort once to place numbers as close as possible to correct indices, then scan to collect all mismatches (duplicates and missing).

3. Step 3: Evaluate other options

   Using hash sets adds extra space; repeated cyclic sorts are inefficient; sorting is O(n log n).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Single cyclic sort + scan finds all mismatches efficiently [OK]

Hint: Single cyclic sort pass + scan finds all mismatches [OK]

Common Mistakes:

• Trying repeated cyclic sorts wastes time
• Adding hash sets breaks O(1) space constraint
• Using sorting loses linear time advantage

5. Suppose the problem is modified so that the input array can contain duplicates and the missing positive range must consider repeated numbers as well (e.g., if 2 appears twice, the missing range should still be correct). Which modification to the cyclic sort approach correctly handles duplicates without causing infinite loops or incorrect missing ranges?

hard

A. Skip swapping when nums[i] == nums[correct_pos] to avoid infinite loops caused by duplicates

B. Use a hash set to track visited numbers during cyclic sort swaps

C. Sort the array first to group duplicates, then apply cyclic sort

D. Increment i unconditionally after every swap regardless of duplicates

Solution

1. Step 1: Understand duplicate handling in cyclic sort

   Duplicates cause infinite swapping if we swap identical numbers repeatedly.

2. Step 2: Modify swap condition

   Adding a check to skip swapping when nums[i] == nums[correct_pos] prevents infinite loops and preserves correctness.

3. Step 3: Confirm other options fail

   Hash sets add extra space, sorting breaks O(n) time, unconditional increment after swap may skip needed swaps.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Skipping swaps on duplicates is standard fix for cyclic sort with duplicates [OK]

Hint: Avoid swapping identical elements to handle duplicates safely [OK]

Common Mistakes:

• Ignoring duplicates causing infinite loops
• Adding extra space unnecessarily