Find the Smallest Missing Positive Range

📋

Problem

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.

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

Edge cases: 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

</>

IDE

def find_smallest_missing_range(nums: list) -> list:public int[] findSmallestMissingRange(int[] nums)vector<int> findSmallestMissingRange(vector<int>& nums)function findSmallestMissingRange(nums)

def find_smallest_missing_range(nums):
    # Write your solution here
    pass

class Solution {
    public int[] findSmallestMissingRange(int[] nums) {
        // Write your solution here
        return new int[]{0,0};
    }
}

#include <vector>
using namespace std;

vector<int> findSmallestMissingRange(vector<int>& nums) {
    // Write your solution here
    return {0,0};
}

function findSmallestMissingRange(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [0, 0]Incorrectly returning zero or negative numbers as missing positive range.✅ Ensure to start checking from positive integer 1, not zero or negatives.

Wrong: [1, 1]Returning [1,1] even when 1 is present in the array.✅ Check presence of 1 before deciding missing range; if 1 present, find next missing positive.

Wrong: [4, 4]Failing to detect gaps between consecutive numbers, returning next after last number instead.✅ Scan sorted array for gaps between consecutive positive numbers and return first gap.

Wrong: [2, 5]Returning a range larger than minimal missing range due to incorrect gap detection.✅ Return the smallest missing range possible, usually a single number range [x, x].

Wrong: Timeout or no outputUsing exponential or quadratic time complexity approach on large inputs.✅ Implement O(n) cyclic sort or hash set approach to handle large inputs efficiently.

✓

Test Cases

Focus on handling empty and minimal input cases correctly.

Consider tricky cases like duplicates and missing 1 explicitly.

Optimize your solution to run efficiently on large inputs.

t1_01basic

Input{"nums":[3,4,-1,1]}

Expected[2,2]

⏱ Performance - must finish in 2000ms

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

💡 Focus on positive integers starting from 1 and check which are missing.

💡 Use sorting or cyclic sort to identify the first missing positive integer.

💡 Return the range starting and ending at the first missing positive integer.

Why it failed: Incorrect output means the code failed to identify the first missing positive integer correctly. Fix by ensuring you check for the smallest positive missing number starting from 1.

✓ Correctly identifies the smallest missing positive integer and returns the minimal range.

t1_02basic

Input{"nums":[1,2,0]}

Expected[3,3]

⏱ Performance - must finish in 2000ms

Array contains 1 and 2, so the smallest missing positive integer is 3, range is [3, 3].

💡 Check for consecutive positive integers starting from 1.

💡 If all numbers from 1 to n are present, the missing number is n+1.

💡 Return [n+1, n+1] when all 1 to n are present.

Why it failed: Fails to handle the case when all numbers from 1 to n are present. Fix by returning [n+1, n+1] if no missing number found in the array.

✓ Correctly returns the next positive integer after the largest consecutive sequence.

t2_01edge

Input{"nums":[]}

Expected[1,1]

⏱ Performance - must finish in 2000ms

Empty array means no positive integers present, so smallest missing range is [1, 1].

💡 Consider what happens when the input array is empty.

💡 The smallest missing positive integer must be 1 in this case.

💡 Return [1, 1] when nums is empty.

Why it failed: Fails to handle empty input, returning invalid or empty output. Fix by returning [1, 1] when nums is empty.

✓ Correctly handles empty input by returning [1, 1].

t2_02edge

Input{"nums":[-5]}

Expected[1,1]

⏱ Performance - must finish in 2000ms

Single negative element means smallest missing positive integer is 1, range [1, 1].

💡 Check behavior with a single negative number.

💡 Negative numbers do not affect the smallest missing positive integer.

💡 Return [1, 1] if no positive numbers are present.

Why it failed: Fails to ignore negative numbers and returns wrong range. Fix by filtering out negatives or ignoring them in logic.

✓ Correctly ignores negatives and returns [1, 1].

t2_03edge

Input{"nums":[1,2,3,4,5]}

Expected[6,6]

⏱ Performance - must finish in 2000ms

Array contains all consecutive numbers from 1 to 5, so smallest missing range is [6, 6].

💡 Check if all numbers from 1 to n are present.

💡 If yes, smallest missing positive integer is n+1.

💡 Return [n+1, n+1] in this case.

Why it failed: Fails to detect complete consecutive sequence and returns incorrect missing range. Fix by returning [n+1, n+1] when all 1 to n present.

✓ Correctly returns [n+1, n+1] for complete consecutive sequences.

t3_01corner

Input{"nums":[1,1,3,3,5,5]}

Expected[2,2]

⏱ Performance - must finish in 2000ms

Duplicates present but smallest missing positive integer is 2, so range is [2, 2].

💡 Duplicates should not affect the missing range calculation.

💡 Ensure your algorithm handles duplicates correctly.

💡 Return the smallest missing positive integer ignoring duplicates.

Why it failed: Fails due to duplicates causing incorrect missing number detection. Fix by ignoring duplicates or using a set.

✓ Correctly handles duplicates and returns the right missing range.

t3_02corner

Input{"nums":[2,3,7,6,8,-1,-10,15]}

Expected[1,1]

⏱ Performance - must finish in 2000ms

1 is missing and smallest positive integer, so range is [1, 1].

💡 Check for missing 1 explicitly as it is the smallest positive integer.

💡 Do not assume array always contains 1.

💡 Return [1, 1] if 1 is missing.

Why it failed: Fails to check for missing 1 and returns wrong range. Fix by explicitly checking presence of 1.

✓ Correctly identifies missing 1 and returns [1, 1].

t3_03corner

Input{"nums":[1,2,4,5,6]}

Expected[3,3]

⏱ Performance - must finish in 2000ms

3 is missing between 2 and 4, so smallest missing range is [3, 3].

💡 Check for gaps between consecutive positive integers.

💡 Return the smallest gap as the missing range.

💡 Return [gap_start, gap_start] for single missing integer.

Why it failed: Fails to detect gaps between consecutive numbers and returns wrong range. Fix by scanning for first gap between sorted positives.

✓ Correctly detects gaps and returns the minimal missing range.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) or O(n log n) solution must complete within 2 seconds.

💡 Use O(n) or O(n log n) approach to handle large input efficiently.

💡 Avoid nested loops or exponential time complexity.

💡 Use cyclic sort or hash set to achieve linear time.

Why it failed: TLE indicates use of exponential or quadratic complexity. Fix by implementing O(n) cyclic sort or hash set approach.

✓ Algorithm runs in O(n) or O(n log n) time confirming efficiency.

Practice

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

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

medium

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

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

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

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

Solution

1. Step 1: Identify loop behavior

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

2. Step 2: Analyze total operations

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

3. Final Answer:

   Option A -> Option A

4. Quick Check:

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

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

Common Mistakes:

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

3. 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 missing numbers in [1, n]?

hard

A. Ignore numbers outside 1 to n during swaps and only swap valid numbers

B. Use a hash set to track all numbers instead of cyclic sort

C. Replace invalid numbers with n+1 before cyclic sort to avoid errors

D. Sort the array first to bring valid numbers to front, then apply cyclic sort

Solution

1. Step 1: Identify invalid numbers impact

   Numbers outside 1 to n cause index errors or invalid swaps in cyclic sort.

2. Step 2: Modify cyclic sort to skip invalid numbers

   Only swap when nums[i] is in [1, n]; ignore or increment i otherwise to maintain O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring invalid numbers preserves cyclic sort correctness [OK]

Hint: Skip invalid numbers to avoid index errors [OK]

Common Mistakes:

• Using hash set loses O(1) space
• Replacing invalid numbers breaks uniqueness
• Sorting adds O(n log n) time

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

hard

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

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

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

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

Solution

1. Step 1: Understand the impact of duplicates

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

2. Step 2: Modify the swap condition

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

3. Step 3: Evaluate other options

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

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Proper swap condition handles duplicates without extra space [OK]

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

Common Mistakes:

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

5. Suppose the array can contain duplicate positive integers and you want to find the kth missing positive number. Which modification to the optimal binary search approach is necessary to handle duplicates correctly?

hard

A. No modification needed; binary search works the same with duplicates.

B. Modify the missing count calculation to account for duplicates by counting unique elements only.

C. Preprocess the array to remove duplicates before applying binary search.

D. Use a hash set to track missing numbers instead of binary search.

Solution

1. Step 1: Understand impact of duplicates

   Duplicates break the assumption that arr[i] - (i + 1) equals missing count because indices no longer correspond to unique elements.

2. Step 2: Identify correct fix

   Removing duplicates restores the strictly increasing property needed for binary search and correct missing count calculation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Preprocessing to unique elements preserves binary search correctness [OK]

Hint: Binary search requires strictly increasing array [OK]

Common Mistakes:

• Assuming duplicates don't affect missing count
• Trying to fix missing count formula without removing duplicates