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 a sorted array of unique positive integers and a positive integer k. You need to find the kth positive integer that is missing from this array. Which algorithmic approach guarantees the most efficient solution in terms of time complexity?

easy

A. Use binary search on the array to find the position where the count of missing numbers reaches k.

B. Use a brute force linear scan counting missing numbers until the kth missing is found.

C. Use dynamic programming to store missing counts and find the kth missing number.

D. Use a greedy approach to iteratively guess missing numbers and verify their presence.

Solution

1. Step 1: Understand the problem constraints

   The array is sorted and contains unique positive integers. We want the kth missing positive number not in the array.

2. Step 2: Identify the optimal approach

   Binary search can be used to find the smallest index where the count of missing numbers is at least k, leveraging the formula missing = arr[mid] - (mid + 1). This yields O(log n) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search exploits sorted order and missing count formula [OK]

Hint: Binary search on missing count is optimal [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing DP with missing count calculation

2. Consider the following buggy code for finding the duplicate and missing numbers:

def find_duplicate_missing(nums):
    i = 0
    n = len(nums)
    while i < n:
        correct_index = nums[i] - 1
        # Bug introduced here
        nums[i], nums[correct_index] = nums[correct_index], nums[i]
        if nums[i] == nums[correct_index]:
            i += 1
    for i in range(n):
        if nums[i] != i + 1:
            return [nums[i], i + 1]
    return [-1, -1]

What is the bug in this code?

medium

A. Swapping without checking if nums[i] != nums[correct_index] causes infinite loop or incorrect swaps

B. Incrementing i only when nums[i] == nums[correct_index] causes skipping needed swaps

C. Returning [-1, -1] when no mismatch is found is incorrect

D. The for loop to find mismatch should start from i=1, not 0

Solution

1. Step 1: Identify the swap condition

   The code swaps nums[i] and nums[correct_index] unconditionally, without checking if they are different.

2. Step 2: Consequence of unconditional swap

   If nums[i] == nums[correct_index], swapping causes no progress and can lead to infinite loop or incorrect behavior.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct code swaps only if nums[i] != nums[correct_index] [OK]

Hint: Always check before swapping to avoid infinite loops [OK]

Common Mistakes:

• Forgetting swap condition leads to infinite loops
• Misplacing increment of i
• Incorrect mismatch detection loop indices

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

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