How to Solve: Find All Numbers Disappeared in an Array

How to Solve: Find All Numbers Disappeared in an Array

(A Complete FAANG-Level Interview Guide)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can solve in-place array problems with O(1) extra space, a skill that separates L4 from L5 engineers at FAANG."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Array indexing & in-place modification – How to use indices as markers without extra space. 2. Cyclic sort – A pattern for rearranging elements to their correct positions in O(n) time. 3. Hash sets vs. in-place marking – Trade-offs between space and time complexity.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every "disappeared numbers" problem.)

1. Clarify Constraints
2. Are duplicates allowed? (If yes, hash set or in-place marking.)
3. Is O(1) space required? (If yes, in-place marking or cyclic sort.)

4. What is the range of numbers? (If 1..n, cyclic sort or negation works well.)

5. Choose the Right Technique

6. O(n) space allowed? → Use a hash set.
7. O(1) space required? → Use in-place negation or cyclic sort.

8. Numbers in 1..n? → Cyclic sort is optimal.

9. Implement the Chosen Approach

10. For in-place negation:
    • Iterate through the array.
    • For each number x, mark nums[abs(x) - 1] as negative.
    • The indices of positive numbers at the end are the missing numbers.

11. For cyclic sort:

    • Swap each number to its correct position (nums[i] should be at nums[i] - 1).
    • After sorting, iterate to find mismatches.

12. Edge Cases

13. Empty array? → Return empty list.
14. All numbers present? → Return empty list.

15. Duplicates? → Ensure marking doesn’t overwrite (use abs()).

16. Optimize & Verify

17. Time complexity: O(n) (two passes).
18. Space complexity: O(1) (in-place) or O(n) (hash set).
19. Test with [4,3,2,7,8,2,3,1] → Should return [5,6].

✅ WORKED EXAMPLES

Example 1 – Basic (In-Place Negation)

Problem: Given an array nums of n integers where nums[i] is in [1, n], return an array of all numbers in [1, n] that do not appear in nums.

Input: nums = [4,3,2,7,8,2,3,1] Output: [5,6]

Step-by-Step Solution: 1. Clarify Constraints:
- Numbers are in 1..n (n = 8).
- O(1) space required (no extra arrays).
- Duplicates exist (2 and 3 appear twice).

1. Choose Technique:

2. In-place negation (O(1) space, handles duplicates).

3. Algorithm:

4. Iterate through nums.
5. For each x, mark nums[abs(x) - 1] as negative.

6. The indices of positive numbers at the end are missing.

7. Code (Python):

def findDisappearedNumbers(nums):

    for num in nums:

        idx = abs(num) - 1

        if nums[idx] > 0:  # Avoid double negation

            nums[idx] = -1


    result = []

    for i in range(len(nums)):

        if nums[i] > 0:

            result.append(i + 1)

    return result

1. Complexity:
2. Time: O(n) (two passes).

3. Space: O(1) (in-place).

4. Why This Works:

5. Negation acts as a "seen" marker without extra space.
6. Duplicates are handled by abs() to avoid overwriting.

Example 2 – Medium (Cyclic Sort)

Problem: Same as above, but without duplicates and O(1) space required.

Input: nums = [4,3,2,7,8,2,3,1] → Wait, duplicates exist! Modified Input: nums = [4,3,2,7,8,1,6,5] (no duplicates) Output: [9] (if n=9)

Step-by-Step Solution: 1. Clarify Constraints:
- No duplicates.
- Numbers in 1..n.
- O(1) space.

1. Choose Technique:

2. Cyclic sort (optimal for 1..n without duplicates).

3. Algorithm:

4. Swap each number to its correct position (nums[i] should be at nums[i] - 1).

5. After sorting, iterate to find mismatches.

6. Code (Python):

def findDisappearedNumbers(nums):

    i = 0

    while i < len(nums):

        correct_pos = nums[i] - 1

        if nums[i] != nums[correct_pos]:

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

        else:

            i += 1


    result = []

    for i in range(len(nums)):

        if nums[i] != i + 1:

            result.append(i + 1)

    return result

1. Complexity:
2. Time: O(n) (each element is swapped at most once).

3. Space: O(1).

4. Why This Works:

5. Cyclic sort places each number in its correct position.
6. Mismatches indicate missing numbers.

Example 3 – Hard (Follow-Up: Find All Missing & Duplicate Numbers)

Problem: Given an array nums of n integers where nums[i] is in [1, n], return: 1. All numbers that do not appear in nums. 2. The number that appears twice.

Input: nums = [4,3,2,7,8,2,3,1] Output: [5,6] (missing), 2 (duplicate)

Step-by-Step Solution: 1. Clarify Constraints:
- Duplicates exist.
- O(1) space required.

1. Choose Technique:

2. In-place negation (marks seen numbers and detects duplicates).

3. Algorithm:

4. Iterate through nums.
5. For each x, mark nums[abs(x) - 1] as negative.
6. If a number is already negative, it’s a duplicate.

7. The indices of positive numbers at the end are missing.

8. Code (Python):

def findErrorNums(nums):

    duplicate = -1

    for num in nums:

        idx = abs(num) - 1

        if nums[idx] < 0:

            duplicate = abs(num)

        else:

            nums[idx] = -1


    missing = -1

    for i in range(len(nums)):

        if nums[i] > 0:

            missing = i + 1

            break


    return [duplicate, missing]

1. Complexity:
2. Time: O(n).

3. Space: O(1).

4. Why This Works:

5. Negation marks seen numbers.
6. A second negative encounter reveals the duplicate.
7. Positive indices reveal missing numbers.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. When you see ‘Find All Numbers Disappeared in an Array,’ here’s your playbook:

1. Clarify constraints first—are duplicates allowed? Is O(1) space required? Numbers in 1..n?
2. If O(n) space is okay, use a hash set. Simple, but not optimal.
3. If O(1) space is required, use in-place negation (negate nums[abs(x)-1] to mark seen numbers). The indices of positive numbers at the end are missing.
4. If numbers are in 1..n without duplicates, cyclic sort is your best friend—swap each number to its correct position, then find mismatches.
5. For follow-ups, like finding duplicates too, negation still works—just check for already-negative numbers.

Test edge cases: empty array, all numbers present, duplicates. And remember—always ask clarifying questions before coding. You’ve got this!

? FINAL NOTES

• Practice Variations:
• LeetCode 448 (Basic)
• LeetCode 442 (Duplicates)
• LeetCode 645 (Missing + Duplicate)
• Time Yourself: Aim for <15 minutes from problem statement to working code.
• Whiteboard First: Sketch the algorithm before coding.

Now go crush that interview! ?