Find All Missing Numbers

▶

Steps

setup

Initialize index i and array length n

Set the pointer i to 0 to start processing from the first element. Store the length of the array in n for boundary checks.

💡 Initializing i and n sets up the iteration over the array for cyclic sorting.

Line:

i = 0
n = len(nums)

💡 We start processing from the beginning of the array and know the array size for loop control.

compare

Calculate correct index for nums[i]

Calculate the correct index for the current number nums[i] by subtracting 1 from its value.

💡 This calculation tells us where the current number should be placed in the array.

Line:

correct = nums[i] - 1

💡 Each number from 1 to n should be at index number-1 for correct placement.

compare

Check and swap nums[i] and nums[correct] if needed

Compare nums[i] with nums[correct]. If they differ, swap to place nums[i] at its correct position.

💡 Swapping moves numbers closer to their correct positions without extra space.

Line:

if nums[i] != nums[correct]:
    nums[i], nums[correct] = nums[correct], nums[i]

💡 Swapping places the current number closer to its correct index.

compare

Continue swapping at i=0 until correct number is placed

Keep calculating correct index and swapping if nums[i] is not at its correct position.

💡 Cyclic sort repeatedly swaps until the correct number is at index i.

Line:

correct = nums[i] - 1
if nums[i] != nums[correct]:
    nums[i], nums[correct] = nums[correct], nums[i]

💡 Multiple swaps at the same index ensure correct placement despite duplicates.

shrink

No swap needed, increment i

Since nums[i] equals nums[correct], no swap is needed. Increment i to move to the next index.

💡 When the current number is at its correct position or duplicate, we move forward.

Line:

else:
    i += 1

💡 We avoid infinite loops by moving forward when no swap is needed.

loop

Process next indices with swaps or moves

Repeat the process of calculating correct index, swapping if needed, or moving forward for i=1 to i=3.

💡 Each index is processed to place numbers correctly or move forward if already correct.

Line:

while i < n:
    correct = nums[i] - 1
    if nums[i] != nums[correct]:
        nums[i], nums[correct] = nums[correct], nums[i]
    else:
        i += 1

💡 The algorithm ensures all numbers are placed or duplicates handled by moving forward.

swap

Swap at i=4 to place 8 correctly

Swap nums[4] and nums[7] to move 8 closer to its correct position.

💡 Swapping places the current number closer to its correct index.

Line:

nums[i], nums[correct] = nums[correct], nums[i]

💡 Swapping handles misplaced numbers even late in the array.

shrink

No swap needed at i=4, increment i

Since nums[i] equals nums[correct], increment i to move forward.

💡 Move forward when the current number is at the correct position.

Line:

else:
    i += 1

💡 Advancing the pointer avoids unnecessary swaps.

loop

Process i=5 with swaps or moves

Calculate correct index and swap if needed for nums[5].

💡 Handle duplicates and misplaced numbers by swapping or moving forward.

Line:

while i < n:
    correct = nums[i] - 1
    if nums[i] != nums[correct]:
        nums[i], nums[correct] = nums[correct], nums[i]
    else:
        i += 1

💡 The algorithm ensures all numbers are placed or duplicates handled by moving forward.

shrink

No swap needed at i=5, increment i

Since nums[i] equals nums[correct], increment i to move forward.

💡 Move forward when the current number is at the correct position.

Line:

else:
    i += 1

💡 Advancing the pointer avoids unnecessary swaps.

loop

Process i=6 and i=7, no swaps needed

At indices 6 and 7, numbers are at correct positions, so increment i to finish sorting.

💡 When numbers are correctly placed, the pointer moves forward.

Line:

else:
    i += 1

💡 The array is now rearranged with numbers at correct indices or duplicates handled.

traverse

Traverse array to find missing numbers

Iterate through the array to find indices where nums[i] != i + 1. These indices + 1 are missing numbers.

💡 This final traversal identifies which numbers are missing by checking mismatches.

Line:

for i in range(n):
    if nums[i] != i + 1:
        missing.append(i + 1)

💡 Numbers missing from the array correspond to indices where the value is incorrect.

traverse

Identify missing number 5 at index 4

At index 4, nums[4] = 3 which is not equal to 5 (index + 1), so 5 is missing.

💡 Mismatch at index 4 means number 5 is missing from the array.

Line:

if nums[i] != i + 1:
    missing.append(i + 1)

💡 Mismatch between index and value reveals missing numbers.

traverse

Identify missing number 6 at index 5

At index 5, nums[5] = 2 which is not equal to 6 (index + 1), so 6 is missing.

💡 Mismatch at index 5 means number 6 is missing from the array.

Line:

if nums[i] != i + 1:
    missing.append(i + 1)

💡 Mismatch between index and value reveals missing numbers.

reconstruct

Complete traversal and finalize missing numbers

After collecting missing numbers, sort them to return the final answer.

💡 Sorting ensures the missing numbers are returned in ascending order.

Line:

return sorted(missing)

💡 The final answer contains all missing numbers from the array.

def findDisappearedNumbers(nums):
    i = 0  # STEP 1
    n = len(nums)  # STEP 1
    while i < n:  # STEP 2 loop
        correct = nums[i] - 1  # STEP 2
        if nums[i] != nums[correct]:  # STEP 3
            nums[i], nums[correct] = nums[correct], nums[i]  # STEP 3-7
        else:
            i += 1  # STEP 5,8,10,11
    missing = []  # STEP 12
    for i in range(n):  # STEP 12 loop
        if nums[i] != i + 1:  # STEP 13,14
            missing.append(i + 1)  # STEP 13,14
    return sorted(missing)  # STEP 15

if __name__ == '__main__':
    print(findDisappearedNumbers([4,3,2,7,8,2,3,1]))  # Output: [5,6]

📊

Find All Missing Numbers - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how cyclic sort efficiently places numbers without extra space and how missing numbers are found by simple index-value checks.

setup

i

4

0

3

1

2

2

7

3

8

4

2

5

3

6

1

7

Result: []

compare

i

4

0

3

1

2

2

correct

7

3

8

4

2

5

3

6

1

7

Result: []

swap

i

7

0

3

1

2

2

4

3

8

4

2

5

correct

3

6

1

7

Result: []

swap

i

3

0

2

1

correct

3

2

4

3

8

4

2

5

7

6

1

7

Result: []

move_right

3

0

i

2

1

3

2

4

3

8

4

2

5

7

6

1

7

Result: []

compare

1

0

2

1

3

2

4

3

i

8

4

2

5

7

6

correct

3

7

Result: []

swap

1

0

2

1

correct

3

2

4

3

i

3

4

2

5

7

6

8

7

Result: []

move_right

1

0

2

1

3

2

4

3

3

4

i

2

5

7

6

8

7

Result: []

compare

1

0

correct

2

1

3

2

4

3

3

4

i

2

5

7

6

8

7

Result: []

move_right

1

0

2

1

3

2

4

3

3

4

2

5

i

7

6

8

7

Result: []

move_right

1

0

2

1

3

2

4

3

3

4

2

5

7

6

8

7

Result: []

traverse

i

1

0

2

1

3

2

4

3

3

4

2

5

7

6

8

7

Result: []

record

1

0

2

1

3

2

4

3

i

3

4

2

5

7

6

8

7

Result: [5]

record

1

0

2

1

3

2

4

3

3

4

i

2

5

7

6

8

7

Result: [5,6]

reconstruct

1

0

2

1

3

2

4

3

3

4

2

5

7

6

8

7

Result: [5,6]

Key Takeaways

✓ Cyclic sort places each number at its correct index by swapping in-place without extra space.

This insight is hard to see from code alone because the swapping logic is subtle and happens conditionally.

✓ Duplicates prevent some swaps and cause the pointer to move forward, avoiding infinite loops.

Understanding when to increment the pointer instead of swapping is key to grasping the algorithm's correctness.

✓ After sorting, missing numbers are identified by checking which indices do not contain the correct number.

This final step is simple but crucial, and watching it visually clarifies how missing numbers are found.

Practice

1. Given the following code snippet, what is the output when the input array is [2, 3, 1, 5, 3]?

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

print(find_duplicate_missing([2, 3, 1, 5, 3]))

easy

A. [3, 5]

B. [5, 4]

C. [3, 4]

D. [2, 4]

Solution

1. Step 1: Trace swaps in the while loop

   Initial array: [2,3,1,5,3] - i=0: nums[0]=2, correct_index=1, swap nums[0] and nums[1] -> [3,2,1,5,3] - i=0: nums[0]=3, correct_index=2, swap nums[0] and nums[2] -> [1,2,3,5,3] - i=0: nums[0]=1, correct_index=0, nums[0]==nums[correct_index], i=1 - i=1: nums[1]=2, correct_index=1, nums[1]==nums[correct_index], i=2 - i=2: nums[2]=3, correct_index=2, nums[2]==nums[correct_index], i=3 - i=3: nums[3]=5, correct_index=4, swap nums[3] and nums[4] -> [1,2,3,3,5] - i=3: nums[3]=3, correct_index=2, nums[3]==nums[correct_index], i=4 - i=4: nums[4]=5, correct_index=4, nums[4]==nums[correct_index], i=5 (exit loop)

2. Step 2: Identify mismatch in second loop

   Check indices: - i=0: nums[0]=1 correct - i=1: nums[1]=2 correct - i=2: nums[2]=3 correct - i=3: nums[3]=3 incorrect, expected 4 -> duplicate=3, missing=4 Return [3,4]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected duplicate and missing [OK]

Hint: Trace swaps carefully to find final array mismatch [OK]

Common Mistakes:

• Confusing duplicate and missing values
• Off-by-one errors in indexing
• Stopping swaps too early

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

3. What is the time complexity of the cyclic sort algorithm that swaps elements to their correct positions in-place for an array of size n containing numbers from 1 to n (possibly with duplicates or missing numbers)?

medium

A. O(n^2) because nested swaps may occur repeatedly

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

C. O(n) average but O(n^2) worst case due to duplicates causing cycles

D. O(n log n) due to sorting overhead

Solution

1. Step 1: Analyze swaps per element

   Each element ideally swaps once, but duplicates can cause repeated swaps forming cycles.

2. Step 2: Consider worst-case scenarios

   Duplicates or missing numbers can cause infinite or repeated swaps, making worst-case O(n^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Duplicates cause repeated swaps, increasing complexity [OK]

Hint: Duplicates cause repeated swaps, increasing worst-case time [OK]

Common Mistakes:

• Assuming always O(n)
• Confusing sorting complexity with cyclic sort
• Ignoring duplicates' effect on swaps

4. What is the time complexity of the cyclic sort approach for finding the corrupt pair in an array of size n with one duplicate and one missing number?

medium

A. O(n log n) due to sorting inside the algorithm

B. O(n^2) because of nested loops swapping elements repeatedly

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

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

Solution

1. Step 1: Identify the main loop behavior

   The while loop runs with index i from 0 to n-1, but swaps only occur when elements are out of place, and each swap places at least one element correctly.

2. Step 2: Analyze swap count and increments

   Each element can be swapped at most once to its correct position, so total swaps ≤ n. The index increments ensure no infinite loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

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

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

Common Mistakes:

• Assuming sorting inside algorithm
• Thinking swaps cause O(n^2)
• Confusing auxiliary space with time

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