Find the Smallest Missing Positive Range

🎯

Find the Smallest Missing Positive Range

mediumCYCLIC_SORTGoogleAmazon

Imagine you manage a warehouse inventory system where product IDs are positive integers starting from 1. You want to find the smallest range of consecutive product IDs missing from the inventory to reorder them efficiently.

💡 This problem is about finding the smallest continuous range of positive integers missing from an unsorted array. Beginners often struggle because the missing range is not just a single number but a consecutive sequence, and naive methods can be inefficient or complicated. Understanding how to rearrange elements in-place to identify missing ranges is key.

📋

Problem Statement

Given an unsorted integer array nums, find the smallest range [start, end] of consecutive positive integers such that none of the numbers in this range appear in nums. The range should be as small as possible (minimum length). If multiple such ranges exist, return the one with the smallest start value. Return the range as a list [start, end].

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

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

Output[2, 2]

The smallest missing positive integer is 2, so the smallest missing range is [2, 2].

Input"[1, 2, 0]"

Output[3, 3]

Numbers 1 and 2 are present, so the smallest missing positive integer is 3, range [3, 3].

Input"[7, 8, 9, 11, 12]"

Output[1, 6]

Numbers 1 through 6 are missing, so the smallest missing positive range is [1, 6].

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

Output[2, 2]

Number 2 is missing and is the smallest missing positive integer, so range is [2, 2].

• All negative numbers → smallest missing range is [1, 1]
• Array contains all consecutive numbers from 1 to n → smallest missing range is [n+1, n+1]
• Array with duplicates → duplicates do not affect missing range calculation
• Array with large gaps → missing range can be multiple numbers long

⚠️

Common Mistakes

Not handling negative numbers and zeros

Incorrect missing range or runtime errors

✅ Ignore or skip non-positive numbers during processing

Infinite swapping loop in cyclic sort

Program hangs or crashes

✅ Check if target position already has correct number before swapping

Returning wrong missing range end

Output range is too large or incorrect

✅ Carefully scan consecutive missing numbers after start to find correct end

Not considering duplicates

Incorrect swaps or missing range calculation

✅ Skip swapping if duplicate number is already in correct position

Assuming missing range is always length 1

Fails on inputs with multiple missing consecutive numbers

✅ Scan forward to find full missing range length

🧠

Brute Force (Sorting + Linear Scan)

💡 This approach exists to build intuition by sorting the array and scanning for missing positive ranges. It is straightforward but not optimal for large inputs.

Intuition

Sort the array, then scan from 1 upwards to find the smallest missing positive range by checking gaps between consecutive positive numbers.

Algorithm

1. Sort the array.
2. Initialize a variable 'expected' to 1, representing the smallest positive integer expected.
3. Iterate through the sorted array, skipping non-positive numbers and duplicates.
4. For each positive number, if it is greater than 'expected', then the missing range is from 'expected' to the number before the current number.
5. If no gaps found, the missing range is from 'expected' to 'expected'.

💡 Sorting helps us see numbers in order, making it easier to spot missing ranges by comparing expected and actual numbers.

</>

Code

def find_smallest_missing_range(nums):
    nums.sort()
    expected = 1
    i = 0
    n = len(nums)
    while i < n and nums[i] < expected:
        i += 1
    while i < n:
        if nums[i] == expected:
            expected += 1
        elif nums[i] > expected:
            return [expected, nums[i] - 1]
        i += 1
    return [expected, expected]

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

Line Notes

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

expected = 1Start looking for missing positive integers from 1

while i < n and nums[i] < expected:Skip all numbers less than expected (non-positive or duplicates)

if nums[i] == expected:If current number matches expected, increment expected to look for next

elif nums[i] > expected:If current number is greater than expected, gap found; return missing range

return [expected, expected]If no gaps found, missing range is the next expected number

import java.util.*;
public class Main {
    public static int[] findSmallestMissingRange(int[] nums) {
        Arrays.sort(nums);
        int expected = 1;
        int i = 0, n = nums.length;
        while (i < n && nums[i] < expected) i++;
        while (i < n) {
            if (nums[i] == expected) expected++;
            else if (nums[i] > expected) return new int[]{expected, nums[i] - 1};
            i++;
        }
        return new int[]{expected, expected};
    }
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        int[] res = findSmallestMissingRange(nums);
        System.out.println("[" + res[0] + ", " + res[1] + "]");
    }
}

Line Notes

Arrays.sort(nums);Sort the array to detect missing ranges easily

int expected = 1;Initialize expected smallest positive integer

while (i < n && nums[i] < expected) i++;Skip non-positive and smaller numbers

if (nums[i] == expected) expected++;Increment expected if current number matches

else if (nums[i] > expected) return new int[]{expected, nums[i] - 1};Return missing range if gap found

return new int[]{expected, expected};Return next expected if no gaps

#include <bits/stdc++.h>
using namespace std;
pair<int,int> findSmallestMissingRange(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int expected = 1, i = 0, n = nums.size();
    while (i < n && nums[i] < expected) i++;
    while (i < n) {
        if (nums[i] == expected) expected++;
        else if (nums[i] > expected) return {expected, nums[i] - 1};
        i++;
    }
    return {expected, expected};
}
int main() {
    vector<int> nums = {3, 4, -1, 1};
    auto res = findSmallestMissingRange(nums);
    cout << "[" << res.first << ", " << res.second << "]\n";
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array to find missing ranges by scanning

int expected = 1;Start checking from smallest positive integer

while (i < n && nums[i] < expected) i++;Skip negative and smaller numbers

if (nums[i] == expected) expected++;Increment expected if current number matches

else if (nums[i] > expected) return {expected, nums[i] - 1};Return missing range if gap found

return {expected, expected};Return next expected if no gaps found

function findSmallestMissingRange(nums) {
    nums.sort((a,b) => a - b);
    let expected = 1, i = 0, n = nums.length;
    while (i < n && nums[i] < expected) i++;
    while (i < n) {
        if (nums[i] === expected) expected++;
        else if (nums[i] > expected) return [expected, nums[i] - 1];
        i++;
    }
    return [expected, expected];
}

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

Line Notes

nums.sort((a,b) => a - b);Sort array ascending to detect missing ranges

let expected = 1;Start from smallest positive integer

while (i < n && nums[i] < expected) i++;Skip negatives and smaller numbers

if (nums[i] === expected) expected++;Increment expected if current number matches

else if (nums[i] > expected) return [expected, nums[i] - 1];Return missing range if gap found

return [expected, expected];Return next expected if no gaps

⏱

Complexity

TimeO(n log n)

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

Sorting takes O(n log n), scanning is O(n). Sorting dominates time complexity.

💡 For n=100,000, sorting takes about 1.5 million operations, which is slow but acceptable for medium inputs.

Interview Verdict: Accepted but not optimal

This approach works but is not efficient for very large inputs; it helps understand the problem and leads to better solutions.

🧠

Better Approach (Hash Set for Presence Check)

💡 This approach uses extra space to track presence of positive numbers, improving time complexity by avoiding sorting.

Intuition

Use a hash set to record all positive numbers, then iterate from 1 upwards to find the smallest missing positive range by checking presence.

Algorithm

1. Create a hash set and add all positive numbers from the array.
2. Initialize 'start' to 1.
3. While 'start' is in the set, increment 'start'.
4. The smallest missing range starts at 'start'.
5. To find the end of the missing range, continue incrementing 'end' from 'start' while 'end' is not in the set.
6. Return [start, end - 1] as the missing range.

💡 Using a hash set allows O(1) presence checks, making it easy to find missing ranges by scanning sequentially.

</>

Code

def find_smallest_missing_range(nums):
    num_set = set(x for x in nums if x > 0)
    start = 1
    while start in num_set:
        start += 1
    end = start
    while end in num_set:
        end += 1
    return [start, end - 1]

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

Line Notes

num_set = set(x for x in nums if x > 0)Create set of positive numbers for O(1) lookups

start = 1Start checking from smallest positive integer

while start in num_set:Increment start until a missing number is found

end = startInitialize end to start to find missing range end

while end in num_set:Increment end while numbers are missing (should be none, but safe)

return [start, end - 1]Return smallest missing positive range

import java.util.*;
public class Main {
    public static int[] findSmallestMissingRange(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) if (num > 0) numSet.add(num);
        int start = 1;
        while (numSet.contains(start)) start++;
        int end = start;
        while (numSet.contains(end)) end++;
        return new int[]{start, end - 1};
    }
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        int[] res = findSmallestMissingRange(nums);
        System.out.println("[" + res[0] + ", " + res[1] + "]");
    }
}

Line Notes

Set<Integer> numSet = new HashSet<>();Use hash set for O(1) presence checks

for (int num : nums) if (num > 0) numSet.add(num);Add only positive numbers to set

int start = 1;Start from smallest positive integer

while (numSet.contains(start)) start++;Find first missing positive integer

int end = start;Initialize end to start for missing range

while (numSet.contains(end)) end++;Find end of missing range

return new int[]{start, end - 1};Return missing range

#include <bits/stdc++.h>
using namespace std;
pair<int,int> findSmallestMissingRange(vector<int>& nums) {
    unordered_set<int> numSet;
    for (int num : nums) if (num > 0) numSet.insert(num);
    int start = 1;
    while (numSet.count(start)) start++;
    int end = start;
    while (numSet.count(end)) end++;
    return {start, end - 1};
}
int main() {
    vector<int> nums = {3, 4, -1, 1};
    auto res = findSmallestMissingRange(nums);
    cout << "[" << res.first << ", " << res.second << "]\n";
    return 0;
}

Line Notes

unordered_set<int> numSet;Use hash set for constant time lookups

for (int num : nums) if (num > 0) numSet.insert(num);Insert only positive numbers

int start = 1;Start from smallest positive integer

while (numSet.count(start)) start++;Find first missing positive integer

int end = start;Initialize end to start for missing range

while (numSet.count(end)) end++;Find end of missing range

return {start, end - 1};Return missing range

function findSmallestMissingRange(nums) {
    const numSet = new Set(nums.filter(x => x > 0));
    let start = 1;
    while (numSet.has(start)) start++;
    let end = start;
    while (numSet.has(end)) end++;
    return [start, end - 1];
}

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

Line Notes

const numSet = new Set(nums.filter(x => x > 0));Create set of positive numbers for O(1) checks

let start = 1;Start from smallest positive integer

while (numSet.has(start)) start++;Find first missing positive integer

let end = start;Initialize end to start for missing range

while (numSet.has(end)) end++;Find end of missing range

return [start, end - 1];Return missing range

⏱

Complexity

TimeO(n)

SpaceO(n)

Building the hash set and scanning for missing range both take O(n) time.

💡 For n=100,000, this approach does about 200,000 operations, which is efficient for large inputs.

Interview Verdict: Accepted and efficient for most cases

This approach is a good improvement over sorting and is acceptable in interviews when extra space is allowed.

🧠

Optimal Approach (Cyclic Sort In-Place)

💡 This approach uses cyclic sort to place each positive number at its correct index, enabling O(n) time and O(1) space solution.

Intuition

Place each number x in position x-1 if possible. Then scan the array to find the first index where the number is not correct, indicating the smallest missing positive range.

Algorithm

1. Iterate through the array and swap elements to their correct positions (nums[i] to nums[nums[i]-1]) if in range and not already correct.
2. After placement, iterate again to find the first index i where nums[i] != i+1.
3. The smallest missing positive integer is i+1.
4. To find the missing range end, continue checking subsequent indices until a number matches the expected value.
5. Return the missing range [start, end].

💡 Cyclic sort rearranges numbers so that the presence or absence of numbers is directly visible by index comparison.

</>

Code

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]
        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]

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

Line Notes

n = len(nums)Store length for boundary checks

while i < n:Iterate to place numbers in correct positions

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

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

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

else: i += 1Move forward if no swap needed

for i in range(n):Find first index where number is incorrect

if nums[i] != i + 1:Mismatch indicates start of missing range

return [n + 1, n + 1]If all correct, missing range is next number

while end <= n and nums[end - 1] != end:Find end of missing range by checking consecutive mismatches

return [start, end - 1]Return smallest missing positive range

import java.util.*;
public class Main {
    public static int[] findSmallestMissingRange(int[] nums) {
        int n = nums.length;
        int i = 0;
        while (i < n) {
            int correctPos = nums[i] - 1;
            if (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[correctPos]) {
                int temp = nums[i];
                nums[i] = nums[correctPos];
                nums[correctPos] = temp;
            } else {
                i++;
            }
        }
        int start = 1;
        int i;
        for (i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                start = i + 1;
                break;
            }
        }
        if (i == n) {
            return new int[]{n + 1, n + 1};
        }
        int end = start;
        while (end <= n && nums[end - 1] != end) {
            end++;
        }
        return new int[]{start, end - 1};
    }
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        int[] res = findSmallestMissingRange(nums);
        System.out.println("[" + res[0] + ", " + res[1] + "]");
    }
}

Line Notes

int n = nums.length;Store array length for bounds

while (i < n)Loop to place numbers correctly

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

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

int temp = nums[i]; nums[i] = nums[correctPos]; nums[correctPos] = temp;Swap to place number in correct position

else i++;Move forward if no swap needed

for (i = 0; i < n; i++)Find first mismatch index

if (nums[i] != i + 1)Mismatch indicates missing range start

if (i == n) return new int[]{n + 1, n + 1};If all numbers correct, missing range is next number

while (end <= n && nums[end - 1] != end)Find end of missing range by checking consecutive mismatches

return new int[]{start, end - 1};Return missing range

#include <bits/stdc++.h>
using namespace std;
pair<int,int> findSmallestMissingRange(vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n) {
        int correctPos = nums[i] - 1;
        if (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[correctPos]) {
            swap(nums[i], nums[correctPos]);
        } else {
            i++;
        }
    }
    int start = 1;
    int i;
    for (i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            start = i + 1;
            break;
        }
    }
    if (i == n) return {n + 1, n + 1};
    int end = start;
    while (end <= n && nums[end - 1] != end) {
        end++;
    }
    return {start, end - 1};
}
int main() {
    vector<int> nums = {3, 4, -1, 1};
    auto res = findSmallestMissingRange(nums);
    cout << "[" << res.first << ", " << res.second << "]\n";
    return 0;
}

Line Notes

int n = nums.size();Store array length

while (i < n)Loop to place numbers correctly

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

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

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

else i++;Move forward if no swap needed

for (i = 0; i < n; i++)Find first mismatch index

if (nums[i] != i + 1)Mismatch indicates missing range start

if (i == n) return {n + 1, n + 1};If all correct, missing range is next number

while (end <= n && nums[end - 1] != end)Find end of missing range

return {start, end - 1};Return missing range

function findSmallestMissingRange(nums) {
    const n = nums.length;
    let i = 0;
    while (i < n) {
        const correctPos = nums[i] - 1;
        if (nums[i] >= 1 && nums[i] <= n && nums[i] !== nums[correctPos]) {
            [nums[i], nums[correctPos]] = [nums[correctPos], nums[i]];
        } else {
            i++;
        }
    }
    let start = 1;
    let i;
    for (i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            start = i + 1;
            break;
        }
    }
    if (i === n) return [n + 1, n + 1];
    let end = start;
    while (end <= n && nums[end - 1] !== end) {
        end++;
    }
    return [start, end - 1];
}

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

Line Notes

const n = nums.length;Store array length

while (i < n)Loop to place numbers correctly

const correctPos = nums[i] - 1;Calculate correct index for current number

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

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

else i++;Move forward if no swap needed

for (i = 0; i < n; i++)Find first mismatch index

if (nums[i] !== i + 1)Mismatch indicates missing range start

if (i === n) return [n + 1, n + 1];If all correct, missing range is next number

while (end <= n && nums[end - 1] !== end)Find end of missing range

return [start, end - 1];Return missing range

⏱

Complexity

TimeO(n)

SpaceO(1)

Each number is swapped at most once, so time is linear. No extra space used except variables.

💡 For n=100,000, this approach does about 100,000 operations, making it very efficient.

Interview Verdict: Accepted and optimal

This is the best approach to code in interviews for this problem, demonstrating mastery of cyclic sort and in-place algorithms.

📊

All Approaches - One-Glance Tradeoffs

💡 The cyclic sort approach is best for interviews due to O(n) time and O(1) space. Hash set is easier but uses extra space. Sorting is simplest but slow.

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 (Hash Set Presence Check)	O(n)	O(n)	No	Yes	Good if extra space allowed
3. Optimal (Cyclic Sort In-Place)	O(n)	O(1)	No	Yes	Code this approach

💼

Interview Strategy

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

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach using sorting and scanning.Explain the hash set approach for better time complexity.Present the optimal cyclic sort approach for O(n) time and O(1) space.Code the optimal approach carefully, test with examples and edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your ability to identify missing positive ranges, optimize from naive to optimal solutions, and write clean, bug-free code.

Common Follow-ups

• What if the array is read-only? → Use extra space like hash set or sorting.
• How to find all missing positive ranges? → Extend cyclic sort and scan for all gaps.

💡 These follow-ups test your adaptability and ability to extend solutions beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Problem asks for smallest missing positive or missing range; 2) Input is unsorted array; 3) Numbers are positive or mixed; 4) Constraints allow O(n) time.

Signature Phrases

'smallest missing positive range''consecutive positive integers missing''unsorted array with positive numbers'

NOT This Pattern When

Problems asking for maximum subarray sums or longest increasing subsequences are different patterns.

Similar Problems

First Missing Positive - find smallest missing positive integer using cyclic sortFind All Missing Numbers - find all missing numbers in range 1 to n using cyclic sort

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

3. Identify the bug in the following code snippet that attempts to find duplicates using cyclic sort:

medium

A. Line with duplicates.append(nums[i]) repeated twice causing duplicates in output

B. Line calculating correct_index = nums[i] - 1 is off by one

C. Condition if nums[i] != nums[correct_index] should be reversed

D. Incrementing i inside else block causes infinite loop

Solution

1. Step 1: Inspect duplicate appending loop

   Duplicates were appended twice for each mismatch, causing repeated entries. The bug is fixed by removing the repeated append.

2. Step 2: Confirm other lines are correct

   Index calculation and swap condition are correct; incrementing i is proper to avoid infinite loop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicate elements appear twice in output due to repeated append [OK]

Hint: Check for repeated append calls causing duplicate outputs [OK]

Common Mistakes:

• Infinite loop due to missing i increment
• Off-by-one errors in index calculation
• Incorrect swap condition reversing logic

4. What is the time complexity of the optimal cyclic sort approach for finding the duplicate and missing numbers in an array of size n?

medium

A. O(n) with additional O(n) space for frequency tracking

B. O(n log n) due to sorting operations

C. O(n^2) in worst case due to nested swaps

D. O(n) because each element is swapped at most once

Solution

1. Step 1: Identify the loops and swaps

   The while loop runs at most n times, each swap places an element correctly, so total swaps ≤ n.

2. Step 2: Confirm no nested repeated work

   Each element is swapped at most once, so total operations are linear in n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear time complexity confirmed by single pass swaps [OK]

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

Common Mistakes:

• Assuming sorting cost O(n log n)
• Thinking swaps can be quadratic
• Confusing extra space usage

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