Find K Missing Positive Numbers

🎯

Find K Missing Positive Numbers

mediumCYCLIC_SORTAmazonGoogle

Imagine you have a list of positive integers representing IDs assigned to users, but some IDs are missing. You want to find the first K missing IDs to assign new users.

💡 This problem is about identifying missing positive numbers in an unsorted array. Beginners often struggle because the missing numbers are not necessarily within the array's range, and naive methods can be inefficient or complicated.

📋

Problem Statement

Given an unsorted array of positive integers and a number K, find the first K missing positive numbers in ascending order.

1 ≤ n ≤ 10^51 ≤ K ≤ 10^51 ≤ arr[i] ≤ 10^9

💡

Example

Input"arr = [3, -1, 4, 5, 5], K = 3"

Output[1, 2, 6]

The missing positive numbers are 1, 2, and 6 in ascending order.

Input"arr = [2, 3, 4], K = 3"

Output[1, 5, 6]

1 is missing before the smallest number, then 5 and 6 after the largest.

• Empty array → first K positive numbers starting from 1
• Array with all consecutive numbers starting from 1 → missing numbers start after max element
• Array with duplicates → duplicates should not affect missing count
• Array with negative numbers and zeros → ignore non-positive numbers

⚠️

Common Mistakes

Not ignoring negative numbers and zeros during cyclic sort

Incorrect swaps or infinite loops

✅ Add condition to only swap numbers in range 1 to n

Not handling duplicates properly

Infinite swapping or incorrect missing numbers

✅ Check if target index already has the correct number before swapping

Not adding missing numbers beyond the array's max value

Missing numbers list is incomplete

✅ After scanning array, add numbers starting from n+1 until K missing numbers are found

Using a set for extra numbers without considering space complexity

High memory usage for large K

✅ Use a boolean array or other space-efficient structure

🧠

Brute Force (Check Every Number Sequentially)

💡 This approach exists to build intuition by directly checking each positive number starting from 1 to see if it is missing. It is simple but inefficient, helping beginners understand the problem's nature.

Intuition

Start from 1 and check if it is in the array. If not, add it to the missing list. Continue checking the next number until we find K missing numbers.

Algorithm

1. Initialize a set with all numbers in the array for O(1) lookups.
2. Start from number 1 and check if it is in the set.
3. If not, add it to the missing list.
4. Continue incrementing the number until we have found K missing numbers.

💡 This algorithm is straightforward but inefficient because it may check many numbers beyond the array's max value.

</>

Code

def find_k_missing_numbers(arr, k):
    nums = set(arr)
    missing = []
    current = 1
    while len(missing) < k:
        if current not in nums:
            missing.append(current)
        current += 1
    return missing

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

Line Notes

nums = set(arr)Create a set for O(1) membership checks

missing = []Initialize list to collect missing numbers

while len(missing) < k:Loop until we find K missing numbers

if current not in nums:Check if current number is missing

import java.util.*;
public class Main {
    public static List<Integer> findKMissingNumbers(int[] arr, int k) {
        Set<Integer> nums = new HashSet<>();
        for (int num : arr) nums.add(num);
        List<Integer> missing = new ArrayList<>();
        int current = 1;
        while (missing.size() < k) {
            if (!nums.contains(current)) missing.add(current);
            current++;
        }
        return missing;
    }

    public static void main(String[] args) {
        System.out.println(findKMissingNumbers(new int[]{3, -1, 4, 5, 5}, 3)); // [1, 2, 6]
    }
}

Line Notes

Set<Integer> nums = new HashSet<>()Use HashSet for O(1) lookups

for (int num : arr) nums.add(num)Populate set with array elements

while (missing.size() < k)Loop until K missing numbers found

if (!nums.contains(current))Check if current number is missing

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

vector<int> findKMissingNumbers(vector<int>& arr, int k) {
    unordered_set<int> nums(arr.begin(), arr.end());
    vector<int> missing;
    int current = 1;
    while ((int)missing.size() < k) {
        if (nums.find(current) == nums.end()) missing.push_back(current);
        current++;
    }
    return missing;
}

int main() {
    vector<int> arr = {3, -1, 4, 5, 5};
    vector<int> res = findKMissingNumbers(arr, 3);
    for (int num : res) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

unordered_set<int> nums(arr.begin(), arr.end())Create hash set for O(1) lookups

vector<int> missing;Store missing numbers

while ((int)missing.size() < k)Loop until K missing numbers found

if (nums.find(current) == nums.end())Check if current number is missing

function findKMissingNumbers(arr, k) {
    const nums = new Set(arr);
    const missing = [];
    let current = 1;
    while (missing.length < k) {
        if (!nums.has(current)) missing.push(current);
        current++;
    }
    return missing;
}

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

Line Notes

const nums = new Set(arr)Use Set for O(1) membership checks

const missing = []Initialize array for missing numbers

while (missing.length < k)Loop until K missing numbers found

if (!nums.has(current))Check if current number is missing

⏱

Complexity

TimeO(n + k * m) where m is average time to check membership (O(1) here), effectively O(n + k)

SpaceO(n) for the set storing array elements

We build a set in O(n) and then check numbers starting from 1 until we find K missing, each check O(1).

💡 For n=100,000 and k=100,000, this approach can be slow because it may check many numbers sequentially.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large inputs, so we need better methods.

🧠

Better Approach (Cyclic Sort + Set for Extra Missing)

💡 This approach uses cyclic sort to place numbers in their correct indices, making it easier to identify missing numbers within the array range. It then collects missing numbers beyond the array's max value.

Intuition

Place each number in its correct index (num - 1) if possible. Then, missing numbers are those indices where the number is incorrect. If we still need more missing numbers, add numbers beyond the max element.

Algorithm

1. Use cyclic sort to place numbers in their correct indices (num - 1) if within range.
2. Traverse the array to find indices where the number is not correct; these indices + 1 are missing numbers.
3. Add these missing numbers to the result list.
4. If we still need more missing numbers, add numbers starting from max(arr) + 1 until we have K missing numbers.

💡 This algorithm efficiently finds missing numbers within the array range and then extends beyond the max element if needed.

</>

Code

def find_k_missing_numbers(arr, k):
    n = len(arr)
    i = 0
    while i < n:
        correct_index = arr[i] - 1
        if 1 <= arr[i] <= n and arr[i] != arr[correct_index]:
            arr[i], arr[correct_index] = arr[correct_index], arr[i]
        else:
            i += 1
    missing = []
    extra_nums = set()
    for i in range(n):
        if arr[i] != i + 1 and len(missing) < k:
            missing.append(i + 1)
            extra_nums.add(arr[i])
    next_num = n + 1
    while len(missing) < k:
        if next_num not in extra_nums:
            missing.append(next_num)
        next_num += 1
    return missing

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

Line Notes

while i < n:Traverse array to place numbers correctly

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

if 1 <= arr[i] <= n and arr[i] != arr[correct_index]:Check if number is in range and misplaced

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

import java.util.*;
public class Main {
    public static List<Integer> findKMissingNumbers(int[] arr, int k) {
        int n = arr.length;
        int i = 0;
        while (i < n) {
            int correctIndex = arr[i] - 1;
            if (arr[i] >= 1 && arr[i] <= n && arr[i] != arr[correctIndex]) {
                int temp = arr[i];
                arr[i] = arr[correctIndex];
                arr[correctIndex] = temp;
            } else {
                i++;
            }
        }
        List<Integer> missing = new ArrayList<>();
        Set<Integer> extraNums = new HashSet<>();
        for (i = 0; i < n && missing.size() < k; i++) {
            if (arr[i] != i + 1) {
                missing.add(i + 1);
                extraNums.add(arr[i]);
            }
        }
        int nextNum = n + 1;
        while (missing.size() < k) {
            if (!extraNums.contains(nextNum)) {
                missing.add(nextNum);
            }
            nextNum++;
        }
        return missing;
    }

    public static void main(String[] args) {
        System.out.println(findKMissingNumbers(new int[]{3, -1, 4, 5, 5}, 3)); // [1, 2, 6]
    }
}

Line Notes

while (i < n)Traverse array to place numbers correctly

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

if (arr[i] >= 1 && arr[i] <= n && arr[i] != arr[correctIndex])Check if number is in range and misplaced

int temp = arr[i]; arr[i] = arr[correctIndex]; arr[correctIndex] = temp;Swap to place number correctly

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

vector<int> findKMissingNumbers(vector<int>& arr, int k) {
    int n = arr.size();
    int i = 0;
    while (i < n) {
        int correctIndex = arr[i] - 1;
        if (arr[i] >= 1 && arr[i] <= n && arr[i] != arr[correctIndex]) {
            swap(arr[i], arr[correctIndex]);
        } else {
            i++;
        }
    }
    vector<int> missing;
    unordered_set<int> extraNums;
    for (int i = 0; i < n && (int)missing.size() < k; i++) {
        if (arr[i] != i + 1) {
            missing.push_back(i + 1);
            extraNums.insert(arr[i]);
        }
    }
    int nextNum = n + 1;
    while ((int)missing.size() < k) {
        if (extraNums.find(nextNum) == extraNums.end()) {
            missing.push_back(nextNum);
        }
        nextNum++;
    }
    return missing;
}

int main() {
    vector<int> arr = {3, -1, 4, 5, 5};
    vector<int> res = findKMissingNumbers(arr, 3);
    for (int num : res) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

while (i < n)Traverse array to place numbers correctly

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

if (arr[i] >= 1 && arr[i] <= n && arr[i] != arr[correctIndex])Check if number is in range and misplaced

swap(arr[i], arr[correctIndex])Swap to place number correctly

function findKMissingNumbers(arr, k) {
    let n = arr.length;
    let i = 0;
    while (i < n) {
        let correctIndex = arr[i] - 1;
        if (arr[i] >= 1 && arr[i] <= n && arr[i] !== arr[correctIndex]) {
            [arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];
        } else {
            i++;
        }
    }
    const missing = [];
    const extraNums = new Set();
    for (let i = 0; i < n && missing.length < k; i++) {
        if (arr[i] !== i + 1) {
            missing.push(i + 1);
            extraNums.add(arr[i]);
        }
    }
    let nextNum = n + 1;
    while (missing.length < k) {
        if (!extraNums.has(nextNum)) {
            missing.push(nextNum);
        }
        nextNum++;
    }
    return missing;
}

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

Line Notes

while (i < n)Traverse array to place numbers correctly

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

if (arr[i] >= 1 && arr[i] <= n && arr[i] !== arr[correctIndex])Check if number is in range and misplaced

[arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]]Swap to place number correctly

⏱

Complexity

TimeO(n + k)

SpaceO(n) due to extraNums set in worst case

Cyclic sort takes O(n), then we find missing numbers in O(n), and add extra missing numbers in O(k).

💡 For n=100,000 and k=100,000, this approach is efficient enough for interviews.

Interview Verdict: Accepted and efficient for large inputs

This approach balances clarity and efficiency, making it ideal for interviews.

🧠

Optimized Approach (Cyclic Sort + Boolean Array for Extra Missing)

💡 This approach improves space usage by using a boolean array instead of a set to track extra numbers beyond the array range, reducing overhead.

Intuition

After cyclic sort, identify missing numbers within the array range. Use a boolean array to mark numbers seen beyond the array range to efficiently find extra missing numbers.

Algorithm

1. Perform cyclic sort to place numbers correctly.
2. Traverse array to find missing numbers within range and collect them.
3. Create a boolean array to mark numbers beyond the array range that appear in the array.
4. Iterate from n+1 upwards, adding numbers not marked in boolean array until K missing numbers are found.

💡 This approach reduces overhead of hash sets by using fixed-size boolean arrays, improving performance.

</>

Code

def find_k_missing_numbers(arr, k):
    n = len(arr)
    i = 0
    while i < n:
        correct_index = arr[i] - 1
        if 1 <= arr[i] <= n and arr[i] != arr[correct_index]:
            arr[i], arr[correct_index] = arr[correct_index], arr[i]
        else:
            i += 1
    missing = []
    extra_nums = [False] * (k + n + 1)
    for i in range(n):
        if arr[i] != i + 1 and len(missing) < k:
            missing.append(i + 1)
        if arr[i] > n and arr[i] < len(extra_nums):
            extra_nums[arr[i]] = True
    next_num = n + 1
    while len(missing) < k:
        if next_num >= len(extra_nums) or not extra_nums[next_num]:
            missing.append(next_num)
        next_num += 1
    return missing

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

Line Notes

extra_nums = [False] * (k + n + 1)Boolean array to track extra numbers beyond array range

if arr[i] != i + 1 and len(missing) < k:Collect missing numbers within array range

if arr[i] > n and arr[i] < len(extra_nums):Mark presence of numbers beyond array range

while len(missing) < k:Add missing numbers beyond array range

import java.util.*;
public class Main {
    public static List<Integer> findKMissingNumbers(int[] arr, int k) {
        int n = arr.length;
        int i = 0;
        while (i < n) {
            int correctIndex = arr[i] - 1;
            if (arr[i] >= 1 && arr[i] <= n && arr[i] != arr[correctIndex]) {
                int temp = arr[i];
                arr[i] = arr[correctIndex];
                arr[correctIndex] = temp;
            } else {
                i++;
            }
        }
        List<Integer> missing = new ArrayList<>();
        boolean[] extraNums = new boolean[k + n + 1];
        for (i = 0; i < n; i++) {
            if (arr[i] != i + 1 && missing.size() < k) {
                missing.add(i + 1);
            }
            if (arr[i] > n && arr[i] < extraNums.length) {
                extraNums[arr[i]] = true;
            }
        }
        int nextNum = n + 1;
        while (missing.size() < k) {
            if (nextNum >= extraNums.length || !extraNums[nextNum]) {
                missing.add(nextNum);
            }
            nextNum++;
        }
        return missing;
    }

    public static void main(String[] args) {
        System.out.println(findKMissingNumbers(new int[]{3, -1, 4, 5, 5}, 3)); // [1, 2, 6]
    }
}

Line Notes

boolean[] extraNums = new boolean[k + n + 1]Boolean array to track extra numbers beyond array range

if (arr[i] != i + 1 && missing.size() < k)Collect missing numbers within array range

if (arr[i] > n && arr[i] < extraNums.length)Mark presence of numbers beyond array range

while (missing.size() < k)Add missing numbers beyond array range

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

vector<int> findKMissingNumbers(vector<int>& arr, int k) {
    int n = arr.size();
    int i = 0;
    while (i < n) {
        int correctIndex = arr[i] - 1;
        if (arr[i] >= 1 && arr[i] <= n && arr[i] != arr[correctIndex]) {
            swap(arr[i], arr[correctIndex]);
        } else {
            i++;
        }
    }
    vector<int> missing;
    vector<bool> extraNums(k + n + 1, false);
    for (int i = 0; i < n; i++) {
        if (arr[i] != i + 1 && (int)missing.size() < k) {
            missing.push_back(i + 1);
        }
        if (arr[i] > n && arr[i] < (int)extraNums.size()) {
            extraNums[arr[i]] = true;
        }
    }
    int nextNum = n + 1;
    while ((int)missing.size() < k) {
        if (nextNum >= (int)extraNums.size() || !extraNums[nextNum]) {
            missing.push_back(nextNum);
        }
        nextNum++;
    }
    return missing;
}

int main() {
    vector<int> arr = {3, -1, 4, 5, 5};
    vector<int> res = findKMissingNumbers(arr, 3);
    for (int num : res) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

vector<bool> extraNums(k + n + 1, false)Boolean vector to track extra numbers beyond array range

if (arr[i] != i + 1 && (int)missing.size() < k)Collect missing numbers within array range

if (arr[i] > n && arr[i] < (int)extraNums.size())Mark presence of numbers beyond array range

while ((int)missing.size() < k)Add missing numbers beyond array range

function findKMissingNumbers(arr, k) {
    let n = arr.length;
    let i = 0;
    while (i < n) {
        let correctIndex = arr[i] - 1;
        if (arr[i] >= 1 && arr[i] <= n && arr[i] !== arr[correctIndex]) {
            [arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];
        } else {
            i++;
        }
    }
    const missing = [];
    const extraNums = new Array(k + n + 1).fill(false);
    for (let i = 0; i < n; i++) {
        if (arr[i] !== i + 1 && missing.length < k) {
            missing.push(i + 1);
        }
        if (arr[i] > n && arr[i] < extraNums.length) {
            extraNums[arr[i]] = true;
        }
    }
    let nextNum = n + 1;
    while (missing.length < k) {
        if (nextNum >= extraNums.length || !extraNums[nextNum]) {
            missing.push(nextNum);
        }
        nextNum++;
    }
    return missing;
}

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

Line Notes

const extraNums = new Array(k + n + 1).fill(false)Boolean array to track extra numbers beyond array range

if (arr[i] !== i + 1 && missing.length < k)Collect missing numbers within array range

if (arr[i] > n && arr[i] < extraNums.length)Mark presence of numbers beyond array range

while (missing.length < k)Add missing numbers beyond array range

⏱

Complexity

TimeO(n + k)

SpaceO(n + k) due to boolean array

Cyclic sort is O(n), scanning is O(n), and adding missing numbers is O(k). Boolean array uses less overhead than a set.

💡 This approach is the most efficient and practical for large inputs in interviews.

Interview Verdict: Accepted and optimal for large inputs

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

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the cyclic sort approach with boolean array optimization is usually the best to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n + k)	O(n)	No	N/A	Mention only - never code
2. Cyclic Sort + Set	O(n + k)	O(n)	No	Yes	Good to explain and code if time permits
3. Cyclic Sort + Boolean Array	O(n + k)	O(n + k)	No	Yes	Best approach to code in interviews

💼

Interview Strategy

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

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Explain the cyclic sort approach and how it helps find missing numbers.Step 4: Discuss optimizations and trade-offs.Step 5: Write clean, tested code for the optimal approach.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize, code correctness, and handling of edge cases.

Common Follow-ups

• What if the array contains negative numbers and zeros? → Ignore them during cyclic sort.
• How to handle very large numbers outside the array range? → Use sets or boolean arrays to track extras.

💡 These follow-ups test your ability to handle input variations and optimize space/time.

🔍

Pattern Recognition

When to Use

1) Need to find missing positive numbers; 2) Input is unsorted; 3) Numbers are positive; 4) K missing numbers requested.

Signature Phrases

first K missing positive numbersunsorted arraypositive integers

NOT This Pattern When

Problems involving negative numbers only or sorted arrays with binary search are different patterns.

Similar Problems

First Missing Positive - find the smallest missing positive numberFind All Numbers Disappeared in an Array - find all missing numbers in range

Practice

1. What is the time complexity of the optimal cyclic sort approach to find the duplicate and missing numbers in an array of size n, and why?

medium

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

B. O(n) but with O(n) extra space for auxiliary arrays

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

D. O(n log n) because of sorting the array

Solution

1. Step 1: Identify the main loop behavior

   The while loop swaps elements to their correct positions. Each swap places at least one element correctly, so total swaps ≤ n.

2. Step 2: Analyze time complexity

   Since each element is moved at most once, the total operations are proportional to n, resulting in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Assuming sorting is involved -> O(n log n)
• Mistaking nested loops inside while as O(n^2)
• Forgetting swaps reduce total operations

2. What is the time complexity of the cyclic sort approach to find the duplicate number in an array of size n, and why?

medium

A. O(n^2) because each swap can cause another iteration over the array

B. O(n log n) due to sorting-like behavior of swaps

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

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

Solution

1. Step 1: Analyze the number of swaps

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

2. Step 2: Confirm linear time complexity

   Since each iteration either swaps or increments index, total operations are O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Assuming swaps cause nested loops leading to O(n²)
• Confusing swaps with sorting complexity O(n log n)
• Forgetting that no extra space is used

3. What is the time complexity of the optimal cyclic sort approach for finding the smallest missing positive range in an array of length n, and why might some candidates mistakenly think it is higher?

medium

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

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

C. O(n^2) because nested loops cause repeated scanning

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

Solution

1. Step 1: Analyze the swapping behavior

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

2. Step 2: Understand loop iterations

   The outer while loop increments i only when no swap occurs, ensuring linear total iterations.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Assuming swaps cause O(n^2)
• Confusing sorting complexity with cyclic sort

4. Consider the following buggy implementation of the cyclic sort approach to find the smallest missing positive range. Identify the line that contains the subtle bug causing incorrect results or infinite loops.

def find_smallest_missing_range(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct_pos = nums[i] - 1
        if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
            # Missing increment of i here
        else:
            i += 1
    start = 1
    for i in range(n):
        if nums[i] != i + 1:
            start = i + 1
            break
    else:
        return [n + 1, n + 1]
    end = start
    while end <= n and nums[end - 1] != end:
        end += 1
    return [start, end - 1]

medium

A. Line missing increment of i after swap inside the while loop

B. Line with the swap: nums[i], nums[correct_pos] = nums[correct_pos], nums[i]

C. Line checking if nums[i] != i + 1 in the for loop

D. Line returning [n + 1, n + 1] if no missing range found

Solution

1. Step 1: Identify the infinite loop cause

   After swapping, the index i is not incremented, so the same index is checked repeatedly causing infinite loop.

2. Step 2: Confirm other lines are correct

   Swap line correctly swaps elements; the for loop and return lines handle missing range detection properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing i increment after swap causes infinite loop or incorrect behavior [OK]

Hint: Always increment index after swap or carefully control loop [OK]

Common Mistakes:

• Forgetting to increment i after swap
• Misplacing swap condition

5. If the input array can contain numbers outside the range 1 to n (including negatives and zeros), which modification to the cyclic sort approach correctly finds all duplicates?

hard

A. Use a hash set to track duplicates instead of cyclic sort

B. Ignore numbers outside 1 to n during cyclic sort and only swap valid numbers

C. Modify cyclic sort to map values to indices using modulo arithmetic

D. Sort the array first and then scan for duplicates

Solution

1. Step 1: Understand cyclic sort limitation

   Cyclic sort relies on values being in 1 to n to map to indices.

2. Step 2: Modify algorithm to skip invalid values

   Ignore values ≤ 0 or > n during swaps to avoid index errors.

3. Step 3: Continue cyclic sort on valid values only

   This preserves O(n) time and O(1) space while handling invalid values.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Skipping invalid values prevents errors and finds duplicates correctly [OK]

Hint: Skip invalid values to keep cyclic sort valid [OK]

Common Mistakes:

• Trying to map invalid values with modulo causes wrong swaps
• Switching to hash set loses O(1) space advantage
• Sorting increases time complexity unnecessarily