Find the Duplicate Number (Cyclic Sort)

🎯

Find the Duplicate Number (Cyclic Sort)

mediumCYCLIC_SORTAmazonFacebookGoogle

Imagine you have a list of employee IDs where one ID is mistakenly duplicated. You need to find that duplicate quickly without extra space.

💡 This problem is about finding a duplicate number in an array where numbers are in a specific range. Beginners often struggle because they try naive methods that are inefficient or use extra space, missing the opportunity to use the array's properties cleverly.

📋

Problem Statement

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. You must not modify the array and use only constant extra space.

1 ≤ n ≤ 10^5nums.length == n + 11 ≤ nums[i] ≤ nOnly one duplicate number exists but it could be repeated multiple times

💡

Example

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

Output2

The number 2 appears twice, so it is the duplicate.

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

Output3

The number 3 appears twice, so it is the duplicate.

• Duplicate is the smallest number (e.g., [1,1,2,3,4]) → output 1
• Duplicate is the largest number (e.g., [1,2,3,4,4]) → output 4
• Duplicate appears multiple times (e.g., [2,2,2,3,4]) → output 2
• Array length is minimum possible (e.g., [1,1]) → output 1

⚠️

Common Mistakes

Not handling the case when duplicate is at the start or end

Code misses duplicate or returns incorrect result

✅ Test edge cases with duplicates at boundaries and adjust logic accordingly

Swapping elements incorrectly in cyclic sort causing infinite loops

Code runs forever or crashes

✅ Ensure swap only happens when elements are not already in correct position and avoid swapping duplicates

Using sorting approach when input modification is forbidden

Violates problem constraints, interviewers reject solution

✅ Clarify constraints and use cycle detection approach instead

Incorrect initialization or update of pointers in Floyd's algorithm

Cycle detection fails or infinite loop occurs

✅ Follow standard Floyd's cycle detection steps carefully

Returning -1 when problem guarantees a duplicate

Unnecessary code path, may confuse interviewer

✅ Return duplicate confidently as problem guarantees existence

🧠

Brute Force (Nested Loops)

💡 This approach exists to establish a baseline understanding. It is simple and intuitive but inefficient, helping beginners grasp the problem before optimizing.

Intuition

Check every pair of elements to see if any two are equal. The first duplicate found is returned.

Algorithm

1. Iterate over each element in the array.
2. For each element, iterate over the rest of the array to check for duplicates.
3. If a duplicate is found, return it immediately.
4. If no duplicates found after all checks, return -1 (though problem guarantees a duplicate).

💡 Nested loops make it easy to understand but hard to scale; beginners often miss the inefficiency here.

</>

Code

def findDuplicate(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return nums[i]
    return -1

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

Line Notes

for i in range(n):Outer loop picks each element to compare

for j in range(i + 1, n):Inner loop compares current element with all subsequent elements

if nums[i] == nums[j]:Check if a duplicate pair is found

return nums[i]Return the duplicate immediately to avoid unnecessary checks

public class Solution {
    public static int findDuplicate(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) {
                    return nums[i];
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,4,2,2};
        System.out.println(findDuplicate(nums)); // Output: 2
    }
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop selects each element

for (int j = i + 1; j < n; j++) {Inner loop compares with subsequent elements

if (nums[i] == nums[j]) {Check for duplicate pair

return nums[i];Return duplicate immediately to optimize runtime

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

int findDuplicate(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }
    return -1;
}

int main() {
    vector<int> nums = {1,3,4,2,2};
    cout << findDuplicate(nums) << endl; // Output: 2
    return 0;
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop picks each element

for (int j = i + 1; j < n; j++) {Inner loop compares with all elements after i

if (nums[i] == nums[j]) {Check if duplicate found

return nums[i];Return duplicate immediately to save time

function findDuplicate(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] === nums[j]) {
                return nums[i];
            }
        }
    }
    return -1;
}

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

Line Notes

for (let i = 0; i < n; i++) {Outer loop selects each element

for (let j = i + 1; j < n; j++) {Inner loop compares with subsequent elements

if (nums[i] === nums[j]) {Check for duplicate

return nums[i];Return duplicate immediately to avoid extra work

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, resulting in n*n operations.

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

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps show initial understanding before optimizing.

🧠

Sorting and Linear Scan

💡 Sorting the array brings duplicates next to each other, making it easier to find duplicates in one pass. This approach is better but modifies the input and uses extra space if sorting is not in-place.

Intuition

Sort the array so duplicates are adjacent, then scan once to find the first pair of equal neighbors.

Algorithm

1. Sort the input array.
2. Iterate through the sorted array from start to end.
3. Compare each element with the next one.
4. Return the element if it equals the next one.

💡 Sorting simplifies the problem but may not be allowed if input modification is forbidden.

</>

Code

def findDuplicate(nums):
    nums.sort()
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            return nums[i]
    return -1

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

Line Notes

nums.sort()Sorts the array to bring duplicates together

for i in range(len(nums) - 1):Iterate through array except last element

if nums[i] == nums[i + 1]:Check if current and next elements are equal

return nums[i]Return the duplicate immediately

import java.util.Arrays;

public class Solution {
    public static int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return nums[i];
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {3,1,3,4,2};
        System.out.println(findDuplicate(nums)); // Output: 3
    }
}

Line Notes

Arrays.sort(nums);Sorts the array in-place

for (int i = 0; i < nums.length - 1; i++) {Traverse array except last element

if (nums[i] == nums[i + 1]) {Check adjacent elements for equality

return nums[i];Return the duplicate immediately

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

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

int main() {
    vector<int> nums = {3,1,3,4,2};
    cout << findDuplicate(nums) << endl; // Output: 3
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sorts the vector in ascending order

for (int i = 0; i < (int)nums.size() - 1; i++) {Iterate through vector except last element

if (nums[i] == nums[i + 1]) {Check if adjacent elements are duplicates

return nums[i];Return the duplicate immediately

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

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

Line Notes

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

for (let i = 0; i < nums.length - 1; i++) {Traverse array except last element

if (nums[i] === nums[i + 1]) {Check adjacent elements for duplicate

return nums[i];Return duplicate immediately

⏱

Complexity

TimeO(n log n)

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

Sorting takes O(n log n), scanning takes O(n).

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

Interview Verdict: Accepted but modifies input

Better than brute force but may not be allowed if input modification is forbidden.

🧠

Cyclic Sort (Optimal In-Place)

💡 This approach uses the cyclic sort pattern to place each number at its correct index. The duplicate is detected when a number is already at its correct position. It is optimal in time and space and does not require extra memory.

Intuition

Since numbers are from 1 to n, each number should be at index number-1. Swap elements to their correct positions until a duplicate is found.

Algorithm

1. Initialize index i to 0.
2. While i < length of array:
3. If nums[i] is not at its correct position (nums[i] != nums[nums[i] - 1]), swap it with the element at its correct position.
4. Else if nums[i] is equal to nums[nums[i] - 1] and i != nums[i] - 1, then nums[i] is the duplicate; return it.
5. If no duplicate found in the loop, return -1.

💡 The swapping ensures each number is placed correctly; duplicate detection happens when a number is already in its correct place.

</>

Code

def findDuplicate(nums):
    i = 0
    while i < len(nums):
        correct_index = nums[i] - 1
        if nums[i] != nums[correct_index]:
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
        else:
            if i != correct_index:
                return nums[i]
            else:
                i += 1
    return -1

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

Line Notes

i = 0Start scanning from the first index

while i < len(nums):Loop until all elements are processed

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

if nums[i] != nums[correct_index]:If current number is not at correct position, swap

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

else:If number is at correct position

if i != correct_index:If duplicate found because number is already at correct index

return nums[i]Return the duplicate number

i += 1Move to next index if no swap or duplicate found

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

    public static void main(String[] args) {
        int[] nums = {3,1,3,4,2};
        System.out.println(findDuplicate(nums)); // Output: 3
    }
}

Line Notes

int i = 0;Initialize index to start scanning

while (i < nums.length) {Loop through array elements

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

if (nums[i] != nums[correctIndex]) {If number not at correct position, swap

int temp = nums[i];Temporary variable for swapping

nums[i] = nums[correctIndex];Swap step 1

nums[correctIndex] = temp;Swap step 2

if (i != correctIndex) {Check if duplicate found

return nums[i];Return duplicate number

i++;Increment index if no swap or duplicate

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

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

int main() {
    vector<int> nums = {3,1,3,4,2};
    cout << findDuplicate(nums) << endl; // Output: 3
    return 0;
}

Line Notes

int i = 0;Start scanning from first index

while (i < (int)nums.size()) {Loop through all elements

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

if (nums[i] != nums[correctIndex]) {If number not at correct position, swap

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

if (i != correctIndex) {Check if duplicate found

return nums[i];Return duplicate number

i++;Increment index if no swap or duplicate

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

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

Line Notes

let i = 0;Initialize index to start scanning

while (i < nums.length) {Loop through array elements

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

if (nums[i] !== nums[correctIndex]) {If number not at correct position, swap

[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];Swap elements using destructuring

if (i !== correctIndex) {Check if duplicate found

return nums[i];Return duplicate number

i++;Increment index if no swap or duplicate

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is swapped at most once to its correct position, resulting in linear time.

💡 For n=1000, this means about 1000 swaps or checks, which is very efficient.

Interview Verdict: Accepted and optimal

This approach is the best for this problem when input modification is allowed.

🧠

Floyd's Tortoise and Hare (Cycle Detection)

💡 This approach treats the array as a linked list where each value points to the index of the next node. The duplicate creates a cycle. Detecting the cycle's start finds the duplicate without modifying the array or using extra space.

Intuition

Use two pointers moving at different speeds to detect a cycle, then find the cycle's entry point which is the duplicate number.

Algorithm

1. Initialize two pointers, slow and fast, at the start of the array.
2. Move slow by one step and fast by two steps until they meet inside the cycle.
3. Reset slow to the start and move both pointers one step at a time.
4. The point where they meet again is the duplicate number.
5. Return the duplicate number.

💡 The cycle detection algorithm cleverly finds the duplicate without modifying the array or extra space.

</>

Code

def findDuplicate(nums):
    slow = nums[0]
    fast = nums[0]
    # Find intersection point
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # Find entrance to cycle
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

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

Line Notes

slow = nums[0]Reset slow to start to find cycle entrance

fast = nums[0]Initialize fast pointer at first element

slow = nums[slow]Move slow pointer one step

fast = nums[nums[fast]]Move fast pointer two steps

if slow == fast:Detect cycle when pointers meet

while slow != fast:Move both pointers one step until they meet

return slowReturn duplicate number found at cycle start

public class Solution {
    public static int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

    public static void main(String[] args) {
        int[] nums = {3,1,3,4,2};
        System.out.println(findDuplicate(nums)); // Output: 3
    }
}

Line Notes

int slow = nums[0];Initialize slow pointer

int fast = nums[0];Initialize fast pointer

slow = nums[slow];Move slow one step

fast = nums[nums[fast]];Move fast two steps

while (slow != fast);Loop until pointers meet (cycle detected)

slow = nums[0];Reset slow to start to find cycle start

while (slow != fast) {Move both pointers one step until they meet

return slow;Return duplicate number

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

int findDuplicate(vector<int>& nums) {
    int slow = nums[0];
    int fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

int main() {
    vector<int> nums = {3,1,3,4,2};
    cout << findDuplicate(nums) << endl; // Output: 3
    return 0;
}

Line Notes

int slow = nums[0];Initialize slow pointer

int fast = nums[0];Initialize fast pointer

slow = nums[slow];Move slow one step

fast = nums[nums[fast]];Move fast two steps

while (slow != fast);Detect cycle when pointers meet

slow = nums[0];Reset slow to start to find cycle start

while (slow != fast) {Move both pointers one step until they meet

return slow;Return duplicate number

function findDuplicate(nums) {
    let slow = nums[0];
    let fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

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

Line Notes

let slow = nums[0];Initialize slow pointer

let fast = nums[0];Initialize fast pointer

slow = nums[slow];Move slow one step

fast = nums[nums[fast]];Move fast two steps

while (slow !== fast);Detect cycle when pointers meet

slow = nums[0];Reset slow to start to find cycle start

while (slow !== fast) {Move both pointers one step until they meet

return slow;Return duplicate number

⏱

Complexity

TimeO(n)

SpaceO(1)

Two pointers traverse the array at different speeds to detect cycle in linear time.

💡 For n=1000, this means about 1000 steps, very efficient and no extra space.

Interview Verdict: Accepted and optimal without modifying input

Best approach when input cannot be modified and constant space is required.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the cyclic sort if input modification is allowed; otherwise, use Floyd's cycle detection. Brute force and sorting are good to mention but not to code.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Sorting and Linear Scan	O(n log n)	O(1) or O(n)	No	N/A	Mention as intermediate approach
3. Cyclic Sort (In-Place)	O(n)	O(1)	No	N/A	Code if input modification allowed
4. Floyd's Tortoise and Hare	O(n)	O(1)	No	N/A	Code if input modification forbidden

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and ask if input modification is allowed.Step 2: Present brute force approach to show understanding.Step 3: Discuss sorting approach and its pros/cons.Step 4: Explain cyclic sort approach as optimal if modification allowed.Step 5: Present Floyd's cycle detection if modification not allowed.Step 6: Code the chosen approach and test with edge cases.

Time Allocation

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

What the Interviewer Tests

Understanding of problem constraints, ability to optimize from brute force to optimal, knowledge of cyclic sort and cycle detection, and clean coding skills.

Common Follow-ups

• What if there are multiple duplicates? → Use hash set or modify approach accordingly.
• Can you solve without modifying the input? → Use Floyd's cycle detection.
• What if numbers are not in range 1 to n? → Cyclic sort and cycle detection won't work directly.
• How to find all duplicates? → Use extended cyclic sort or hash map.

💡 These follow-ups test your flexibility and deeper understanding of the problem constraints and variants.

🔍

Pattern Recognition

When to Use

1) Array contains numbers in range 1 to n; 2) Need to find duplicates or missing numbers; 3) Constraints allow in-place swaps or cycle detection; 4) Problem hints at indexing or cycle properties.

Signature Phrases

array contains n+1 integers between 1 and nfind the duplicate numberdo not modify the arrayconstant extra space

NOT This Pattern When

Sorting problems without range constraints, hash map based duplicate detection

Similar Problems

Find All Duplicates in an Array - similar cyclic sort techniqueFirst Missing Positive - uses cyclic sort to find missing number

Practice

1. Given the following code snippet implementing the cyclic sort approach, what is the returned output when the input array is [2, 2, 3]?

easy

A. [2, 1]

B. [2, 1]

C. [2, 1]

D. [2, 1]

Solution

1. Step 1: Trace the cyclic sort swaps

   Initial array: [2, 2, 3]. i=0, nums[0]=2, correct_index=1. nums[0] == nums[1], so increment i to 1. i=1, nums[1]=2, correct_index=1, same index, increment i to 2. i=2, nums[2]=3, correct_index=2, correct place, increment i to 3.

2. Step 2: Identify mismatch in final array

   Final array remains [2, 2, 3]. Check indices: i=0 expects 1 but has 2 (duplicate), i=1 expects 2 and has 2 (correct), i=2 expects 3 and has 3 (correct). The mismatch at i=0 means duplicate=2, missing=1.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected corrupt pair [2, 1] [OK]

Hint: Trace swaps carefully; duplicates cause no swap but increment index [OK]

Common Mistakes:

• Off-by-one in indexing
• Returning wrong pair order
• Missing increment after swap

2. 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

3. What is the time complexity of the optimal approach that uses cyclic sort combined with a boolean array to find the first k missing positive numbers in an array of size n?

medium

A. O(n * k) due to nested loops scanning for missing numbers

B. O(n + k) because cyclic sort is O(n) and scanning for missing numbers is O(k)

C. O(n log n) due to sorting inside cyclic sort

D. O(n + k + n*k) due to extra space scanning

Solution

1. Step 1: Analyze cyclic sort complexity

   Cyclic sort runs in O(n) because each number is swapped at most once to its correct position.

2. Step 2: Analyze missing number scanning

   Scanning for missing numbers and filling missing list takes O(k) time, as it may extend beyond array length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of O(n) + O(k) = O(n + k) [OK]

Hint: Cyclic sort is linear; extra scanning adds O(k) [OK]

Common Mistakes:

• Assuming sorting inside cyclic sort causes O(n log n)
• Confusing nested loops causing O(n*k)
• Ignoring that scanning missing numbers is linear in k

4. Examine the following buggy implementation of the cyclic sort approach to find the missing number:

def missingNumber(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct = nums[i]
        if nums[i] != nums[correct]:  # Bug here
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i:
            return i
    return n

What is the bug in this code?

medium

A. The condition misses checking if correct < n, causing index errors

B. The swap line incorrectly swaps nums[i] and nums[correct]

C. The increment i += 1 is inside the else block, causing infinite loops

D. The final for loop should return n-1 instead of n when no mismatch found

Solution

1. Step 1: Identify the missing boundary check

   The condition lacks 'correct < n' check, so if nums[i] == n, nums[correct] causes index out of range.

2. Step 2: Consequences of missing check

   Without this, the code may crash or loop infinitely when encountering the number n, which is outside array indices.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding 'correct < n' prevents out-of-bounds errors [OK]

Hint: Always check index bounds before accessing array [OK]

Common Mistakes:

• Forgetting boundary check leads to runtime errors
• Misplacing increment causing infinite loops
• Incorrect swap lines that look correct

5. Suppose the problem changes: the array can contain repeated numbers that can be reused infinitely many times. Which modification to the optimal approach is necessary to correctly find the first k missing positive numbers?

hard

A. Use a frequency map instead of cyclic sort to track counts and find missing numbers.

B. Keep the cyclic sort but add a visited set to avoid infinite swaps due to reuse.

C. Replace cyclic sort with a brute force check for each number from 1 upwards until k missing are found.

D. Use a priority queue to generate missing numbers dynamically considering reuse.

Solution

1. Step 1: Understand reuse impact

   Infinite reuse means cyclic sort assumptions break because numbers can appear multiple times and be reused infinitely.

2. Step 2: Identify correct approach

   A frequency map tracks counts of each number, allowing detection of missing positives even with infinite reuse.

3. Step 3: Why other options fail

   Adding visited set won't prevent infinite swaps due to reuse. Brute force is inefficient. Priority queue adds overhead without correctness guarantee.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency map handles reuse correctly and efficiently [OK]

Hint: Reuse breaks cyclic sort; frequency map needed [OK]

Common Mistakes:

• Trying to patch cyclic sort with visited sets
• Assuming brute force is acceptable for large k
• Using priority queues unnecessarily