Find the Smallest Missing Positive Range

▶

Steps

setup

Initialize variables and start with i=0

We start with the input array [3, 4, -1, 1] and set i to 0 to begin processing from the first element.

💡 Setting i=0 means we will check the first element to see if it is in the correct position or needs to be swapped.

Line:

n = len(nums)
i = 0

💡 Initialization prepares for the cyclic sort by setting the iteration index.

compare

Calculate correct position for nums[i]=3

Calculate the correct position for the current element 3, which should be at index 2 (3 - 1).

💡 Finding the correct position helps us know where this element should be placed if it is in the valid range.

Line:

correct_pos = nums[i] - 1

💡 The correct position for a number x is x-1 if x is positive and within array bounds.

compare

Check if nums[i] should be swapped with nums[correct_pos]

Since nums[i]=3 is in range 1 to n and not equal to nums[correct_pos]=nums[2]=-1, we decide to swap them.

💡 Swapping places the number at its correct index, moving closer to a sorted state where nums[i] = i+1.

Line:

if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:

💡 This condition ensures only valid numbers are placed correctly and avoids infinite swaps.

swap

Swap nums[i] and nums[correct_pos]

Swap the elements at indices 0 and 2: 3 and -1. The array becomes [-1, 4, 3, 1].

💡 Swapping places the number 3 at its correct index 2, moving the array closer to sorted order.

Line:

nums[i], nums[correct_pos] = nums[correct_pos], nums[i]

💡 Swapping is the core operation that rearranges elements in cyclic sort.

compare

Re-evaluate nums[i] after swap at i=0

Now nums[i] = -1 at index 0. Calculate correct_pos = -2, which is invalid, so no swap.

💡 Negative numbers or out-of-range values are ignored and we move to the next index.

Line:

correct_pos = nums[i] - 1
if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:
    ...
else:
    i += 1

💡 Only positive numbers within array length are placed; others are skipped.

compare

Increment i to 1 and calculate correct_pos for nums[1]=4

At index 1, nums[i] = 4, correct_pos = 3 (4 - 1).

💡 We check if 4 is in the correct position or needs swapping.

Line:

i += 1
correct_pos = nums[i] - 1

💡 We continue cyclic sort by processing the next element.

swap

Swap nums[i]=4 with nums[correct_pos]=1

Swap elements at indices 1 and 3: 4 and 1. Array becomes [-1, 1, 3, 4].

💡 Placing 4 at index 3 is correct; now check the new element at index 1.

Line:

nums[i], nums[correct_pos] = nums[correct_pos], nums[i]

💡 Swapping moves elements closer to their correct positions.

compare

Re-evaluate nums[i]=1 at index 1

Calculate correct_pos = 0 for nums[i]=1. Since nums[1] != nums[0], swap needed.

💡 1 should be at index 0, so we swap to place it correctly.

Line:

correct_pos = nums[i] - 1
if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:

💡 Repeated swaps may be needed until the current index holds the correct number.

swap

Swap nums[i]=1 with nums[correct_pos]=-1

Swap elements at indices 1 and 0: 1 and -1. Array becomes [1, -1, 3, 4].

💡 Now 1 is correctly placed at index 0; check the new element at index 1.

Line:

nums[i], nums[correct_pos] = nums[correct_pos], nums[i]

💡 Swapping places the smallest positive number at the start.

compare

Check nums[i]=-1 at index 1, no swap, increment i

nums[i] = -1 is invalid for swapping, so increment i to 2.

💡 Negative numbers are skipped as they cannot be placed in the positive range.

Line:

else:
    i += 1

💡 The algorithm moves forward when no swap is possible.

compare

Check nums[i]=3 at index 2, already correct

nums[i] = 3 is at index 2 which is correct (3 - 1 = 2), so increment i to 3.

💡 No swap needed if element is already at correct position.

Line:

if nums[i] != nums[correct_pos]:
    ...
else:
    i += 1

💡 Correctly placed elements are left untouched.

compare

Check nums[i]=4 at index 3, already correct

nums[i] = 4 is at index 3 which is correct (4 - 1 = 3), so increment i to 4 ending the loop.

💡 All elements are now either correctly placed or invalid.

Line:

if nums[i] != nums[correct_pos]:
    ...
else:
    i += 1

💡 Cyclic sort phase is complete.

traverse

Start scanning for smallest missing positive integer

Iterate from i=0 to find first index where nums[i] != i+1. At i=1, nums[1] = -1 != 2, so start=2.

💡 This identifies the smallest missing positive integer by checking placement correctness.

Line:

for i in range(n):
    if nums[i] != i + 1:
        start = i + 1
        break

💡 Mismatch between index and value reveals missing number.

insert

Initialize end of missing range to start

Set end = start = 2 to begin finding the extent of the missing range.

💡 We will check subsequent indices to find how far the missing range extends.

Line:

end = start

💡 Starting point for missing range is the smallest missing positive integer.

compare

Check if nums[end-1] matches end to expand missing range

Check nums[1] = -1 != 2, so condition fails and we do not expand the range.

💡 If the number at end-1 does not equal end, the missing range ends here.

Line:

while end <= n and nums[end - 1] != end:
    end += 1

💡 The missing range is continuous until a number matches the expected value.

reconstruct

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

Return [2, 2] as the smallest missing positive range since end was not incremented.

💡 The missing range is from 2 to 2, indicating only the number 2 is missing.

Line:

return [start, end - 1]

💡 The algorithm outputs the correct missing range after rearranging and scanning.

def find_smallest_missing_range(nums):
    n = len(nums)  # STEP 1
    i = 0  # STEP 1
    while i < n:  # STEP 2-12
        correct_pos = nums[i] - 1  # STEP 2,6,8
        if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:  # STEP 3,7,8
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]  # STEP 4,7,9
        else:
            i += 1  # STEP 5,10,11,12
    start = 1  # STEP 13
    for i in range(n):  # STEP 13
        if nums[i] != i + 1:
            start = i + 1
            break
    else:
        return [n + 1, n + 1]
    end = start  # STEP 14
    while end <= n and nums[end - 1] != end:  # STEP 15
        end += 1
    return [start, end - 1]  # STEP 16

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

📊

Find the Smallest Missing Positive Range - Watch the Algorithm Execute, Step by Step

Watching each swap and pointer movement reveals how cyclic sort efficiently organizes the array and how the missing range is detected without extra space.

compare

i

3

0

4

1

-1

2

1

3

compare

i

3

0

4

1

correct_pos

-1

2

1

3

compare

i

3

0

4

1

correct_pos

-1

2

1

3

swap

i

-1

0

4

1

correct_pos

3

2

1

3

move_right

i

-1

0

4

1

3

2

1

3

compare

-1

0

i

4

1

3

2

correct_pos

1

3

swap

-1

0

i

1

1

3

2

correct_pos

4

3

compare

correct_pos

-1

0

i

1

1

3

2

4

3

swap

correct_pos

1

0

i

-1

1

3

2

4

3

move_right

1

0

-1

1

i

3

2

4

3

move_right

1

0

-1

1

3

2

i

4

3

move_right

1

0

-1

1

3

2

4

3

compare

1

0

i

-1

1

3

2

4

3

record

1

0

end

-1

1

3

2

4

3

compare

1

0

end

-1

1

3

2

4

3

record

1

0

end

-1

1

3

2

4

3

Result: [2,2]

Key Takeaways

✓ Cyclic sort rearranges the array so that each positive integer x is placed at index x-1 if possible.

This insight is hard to see from code alone because the swaps happen conditionally and in-place without extra space.

✓ The smallest missing positive integer is the first index where the value does not match the expected i+1.

Visually scanning the array after sorting makes it clear how the missing number is identified.

✓ The missing range extends until the first index where the number matches the expected value, showing continuous missing numbers.

This step reveals how the algorithm finds not just one missing number but the entire missing range.

Practice

1. Given the following code snippet, what is the output when calling findErrorNums([1, 2, 2, 4])?

easy

A. [2, 4]

B. [3, 2]

C. [2, 3]

D. [1, 3]

Solution

1. Step 1: Trace the cyclic sort swaps

   Initial array: [1, 2, 2, 4]. The duplicate 2 causes a swap to place numbers correctly except index 2 which remains 2.

2. Step 2: Identify mismatch after sorting

   After sorting, array is [1, 2, 2, 4]. At index 2, expected 3 but found 2 -> duplicate=2, missing=3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected duplicate and missing pair [OK]

Hint: Mismatch found where index+1 != value after cyclic sort [OK]

Common Mistakes:

• Confusing duplicate and missing order
• Off-by-one errors in indexing
• Returning wrong pair from loop

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 binary search approach to find the kth missing positive number in a sorted array of length n?

medium

A. O(n)

B. O(log n)

C. O(k log n)

D. O(n log k)

Solution

1. Step 1: Analyze the binary search loop

   The algorithm performs a binary search on the array indices, halving the search space each iteration, resulting in O(log n) iterations.

2. Step 2: Confirm constant work per iteration

   Each iteration computes missing count in O(1) time, so total time is O(log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search on array length n -> O(log n) [OK]

Hint: Binary search halves search space each iteration [OK]

Common Mistakes:

• Confusing k with n in complexity
• Assuming linear scan dominates

4. The following code attempts to find the kth missing positive number using binary search. Which line contains a subtle bug that causes incorrect results when the kth missing number is less than the first element of the array?

medium

A. Line 6: if missing <= k:

B. Line 4: mid = (low + high) // 2

C. Line 8: low = mid + 1

D. Line 10: return k + high + 1

Solution

1. Step 1: Identify the bug in condition

   The condition uses <= instead of < when comparing missing and k. This causes the binary search to move low pointer incorrectly when missing equals k.

2. Step 2: Explain impact on edge cases

   When kth missing is less than arr[0], missing counts start at zero, and using <= causes the search to skip the correct boundary, returning wrong results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing <= to < fixes boundary handling [OK]

Hint: Check strict inequality in binary search condition [OK]

Common Mistakes:

• Using <= instead of <
• Incorrect return formula

5. Suppose the input array can contain numbers outside the range 1 to n, including negatives and zeros, and duplicates. Which modification to the cyclic sort algorithm ensures correct placement of numbers 1 to n at indices 0 to n-1 while ignoring invalid numbers?

hard

A. Swap elements only if arr[i] is in [1, n] and arr[i] != arr[arr[i] - 1], else increment i.

B. Use an extra array of size n to place valid numbers at index num-1, ignoring invalids.

C. Sort the array first, then remove invalid numbers and duplicates.

D. Ignore duplicates by skipping swaps when arr[i] == arr[arr[i] - 1] without checking range.

Solution

1. Step 1: Understand input constraints

   Input may have invalid numbers (negatives, zeros, > n) and duplicates that break in-place cyclic sort.

2. Step 2: Use extra array for placement

   Creating a separate array of size n and placing valid numbers at index num-1 ensures correct placement ignoring invalids and duplicates.

3. Step 3: Avoid in-place swaps that cause index errors or infinite loops

   Extra space approach is safer and simpler for this variant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Extra array handles invalid and duplicate numbers cleanly [OK]

Hint: Extra array avoids invalid index and duplicate issues [OK]

Common Mistakes:

• Ignoring invalid range checks
• Trying to fix in-place swaps with invalid numbers
• Not handling duplicates properly