Find the Missing Number

▶

Steps

setup

Initial Array State

We start with the unsorted input array [3, 0, 1]. The algorithm will first sort this array to prepare for index comparison.

💡 Sorting ensures the numbers are in order so that each index should match the number if none are missing.

Line:

nums.sort()

💡 Sorting is a prerequisite to detect the missing number by comparing indices to values.

setup

Array After Sorting

The array is now sorted to [0, 1, 3]. This order allows direct comparison of each element with its index.

💡 Sorted order means if no number is missing, element at index i should equal i.

Line:

nums.sort()

💡 Sorting aligns values with indices for straightforward detection of missing numbers.

compare

Compare index 0 with element 0

Compare the element at index 0 (value 0) with the index itself (0). They match, so continue.

💡 Matching index and value means no missing number at this position.

Line:

for i, num in enumerate(nums):
    if i != num:

💡 If index equals element, the missing number is not at this position.

compare

Compare index 1 with element 1

Compare the element at index 1 (value 1) with the index 1. They match, so continue.

💡 Matching index and value means no missing number at this position.

Line:

for i, num in enumerate(nums):
    if i != num:

💡 Index and element equality means missing number is not here.

compare

Compare index 2 with element 3

Compare the element at index 2 (value 3) with the index 2. They do not match, indicating the missing number is 2.

💡 Mismatch means the missing number is the current index.

Line:

for i, num in enumerate(nums):
    if i != num:
        return i

💡 First mismatch between index and element reveals the missing number.

reconstruct

Return missing number 2

The algorithm returns 2 as the missing number because the mismatch was detected at index 2.

💡 Returning the index at mismatch gives the missing number directly.

Line:

return i

💡 The missing number is the first index where element and index differ.

compare

Edge Case: All numbers present

If no mismatch is found in the loop, the missing number is the length of the array.

💡 This handles the case where the missing number is the largest number n.

Line:

return len(nums)

💡 If all indices match elements, missing number is n.

reconstruct

Summary: Missing number found

The missing number 2 is confirmed as the output of the algorithm for the input [3,0,1].

💡 This final step confirms the algorithm's correctness on the example.

Line:

print(missingNumber([3,0,1]))

💡 The algorithm successfully identifies the missing number by sorting and comparing indices.

compare

Visualizing bit positions

Highlighting the least significant bits of the numbers to show their binary form during comparison.

💡 Understanding binary representation helps grasp bit-level operations in other algorithms.

Line:

for i, num in enumerate(nums):

💡 Binary bits reveal the numeric values compared at each step.

reconstruct

End of Algorithm

The algorithm ends after returning the missing number 2, completing the process.

💡 The final output is the missing number found by the algorithm.

Line:

print(missingNumber([3,0,1]))

💡 The algorithm terminates successfully with the correct answer.

def missingNumber(nums):  # STEP 1: Start
    nums.sort()  # STEP 2: Sort array
    for i, num in enumerate(nums):  # STEP 3-5: Iterate and compare
        if i != num:  # STEP 5: Detect mismatch
            return i  # STEP 6: Return missing number
    return len(nums)  # STEP 7: Return n if no mismatch

if __name__ == '__main__':  # STEP 8: Run example
    print(missingNumber([3,0,1]))  # Output: 2

📊

Find the Missing Number - Watch the Algorithm Execute, Step by Step

Watching each comparison and decision helps you understand how sorting and linear scan reveal the missing number efficiently.

Sorting array

A

0

1

1

=3

B

Sorted array

A

0

0

0

0

0

0

0

0

=0

B

Compare index 0 and num 0

A

0

0

0

0

0

0

0

0

=0

B

💡 Index 0 matches element 0

Compare index 1 and num 1

A

0

1

=1

B

💡 Index 1 matches element 1

Compare index 2 and num 3

A

0

1

1

1

=3

B

💡 Mismatch found: index 2 != element 3

Return missing number

A

0

1

0

0

=2

B

────────

=

0

1

0

0

=2

💡 Missing number 2 identified and returned

Return length if no mismatch

A

0

1

1

1

=3

B

────────

=

0

1

1

1

=3

💡 Missing number is n when all match

Final missing number output

A

0

1

0

0

=2

B

────────

=

0

1

0

0

=2

💡 Output confirmed as 2

Highlight bits of num 1

A

0

1

=1

B

💡 Binary form of 1

Algorithm complete

A

0

1

0

0

=2

B

────────

=

0

1

0

0

=2

💡 Final missing number output

Key Takeaways

✓ Sorting the array aligns numbers with their indices, enabling direct comparison to find the missing number.

This insight is hard to see from code alone because the importance of sorting for index alignment is implicit.

✓ The first index where the element does not match the index is the missing number.

Visualizing each comparison step clarifies why the mismatch reveals the missing number immediately.

✓ If all elements match their indices, the missing number is the length of the array.

This fallback case is often overlooked but is critical for correctness; the visualization highlights this clearly.

Practice

1. You are given an array of integers where each integer is between 1 and n (inclusive), and some elements appear twice while others appear once. Which algorithmic approach guarantees finding all duplicate elements in O(n) time and O(1) extra space?

easy

A. Cyclic sort to place each number at its correct index, then scanning for mismatches

B. Using a hash set to track seen elements and identify duplicates

C. Sorting the array and then scanning for consecutive duplicates

D. Applying a dynamic programming approach to count occurrences

Solution

1. Step 1: Understand problem constraints

   The array contains numbers from 1 to n, allowing index-based placement.

2. Step 2: Identify approach that uses in-place swaps

   Cyclic sort places each number at index = number - 1, enabling O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cyclic sort exploits value-index mapping for optimal duplicate detection [OK]

Hint: Use cyclic sort for O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming sorting is always O(n) time
• Believing hash sets use O(1) space
• Confusing DP applicability for duplicates

2. You are given an array containing numbers from 1 to n, but some numbers appear twice and others are missing. Which algorithmic approach guarantees finding all missing numbers in O(n) time and O(1) extra space?

easy

A. In-place cyclic sort that places each number at its correct index

B. Sorting the array and then scanning for missing numbers

C. Using a hash set to track presence of numbers

D. Dynamic programming to count occurrences and identify missing numbers

Solution

1. Step 1: Understand problem constraints

   The array contains numbers from 1 to n with duplicates and missing numbers, requiring an O(n) time and O(1) space solution.

2. Step 2: Identify the approach that fits constraints

   In-place cyclic sort rearranges numbers so each number is at index = number - 1, enabling detection of missing numbers without extra space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only cyclic sort achieves O(n) time and O(1) space for this problem [OK]

Hint: Optimal approach uses in-place cyclic sort [OK]

Common Mistakes:

• Assuming sorting is O(n) time
• Using extra space violates O(1) space
• Confusing DP with counting problems

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

4. Consider the following Python function that finds the first k missing positive numbers using cyclic sort and a boolean array. What is the output of find_k_missing_numbers([3, -1, 4, 5, 5], 3)?

easy

A. [2, 3, 6]

B. [1, 2, 3]

C. [1, 4, 6]

D. [1, 2, 6]

Solution

1. Step 1: Perform cyclic sort on input [3, -1, 4, 5, 5]

   After sorting, the array becomes [1, -1, 3, 4, 5] with 1 at index 0, -1 at index 1, 3 at index 2, 4 at index 3, and 5 at index 4. Negative numbers are ignored in placement.

2. Step 2: Identify missing numbers and extras

   Missing numbers are 2 (since index 1 != 2), and since k=3, the next missing number beyond array length is 6. So missing = [1, 2, 6].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected missing positives [OK]

Hint: Cyclic sort places numbers correctly; missing are indices not matching values [OK]

Common Mistakes:

• Confusing indices and values after cyclic sort
• Forgetting to add missing numbers beyond array length
• Miscounting duplicates as missing

5. If the problem is changed so that numbers can appear multiple times (duplicates can appear more than twice), which modification to the cyclic sort approach is necessary to correctly find any duplicate?

hard

A. Use Floyd's Tortoise and Hare algorithm instead because cyclic sort fails with multiple duplicates

B. No modification needed; the current cyclic sort approach works for multiple duplicates

C. Modify the code to continue scanning after finding the first duplicate to find all duplicates

D. Add a hash set to track visited numbers since cyclic sort assumes only one duplicate

Solution

1. Step 1: Understand cyclic sort assumption

   Cyclic sort assumes exactly one duplicate; multiple duplicates break the unique mapping to indices.

2. Step 2: Identify solution for multiple duplicates

   Using a hash set tracks seen numbers and detects any duplicate regardless of count.

3. Step 3: Why other options fail

   Continuing cyclic sort won't find all duplicates; Floyd's algorithm detects one cycle only; no modification fails on multiple duplicates.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Hash set handles multiple duplicates correctly [OK]

Hint: Cyclic sort assumes one duplicate; hash set needed for multiple [OK]

Common Mistakes:

• Assuming cyclic sort works unchanged for multiple duplicates
• Thinking Floyd's algorithm finds all duplicates
• Trying to modify cyclic sort without extra space