LeetCode 448: Find All Numbers Disappeared in an Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 448: Find All Numbers Disappeared in an Array?

In LeetCode 448: Find All Numbers Disappeared in an Array, you’re given an array nums of length n, where each element is an integer from 1 to n, and some numbers appear twice while others are missing. Your task is to return a list of all numbers from 1 to n that don’t appear in the array, using O(n) time and no extra space beyond the output. For example, in [4, 3, 2, 7, 8, 2, 3, 1], the missing numbers are 5 and 6. It’s like checking a roster where some students are marked present twice, leaving others unaccounted for.

Problem Statement

• Input: nums (List[int])—array of integers.
• Output: List[int]—all missing numbers from 1 to n.
• Rules:
• n = nums.length.
• 1 ≤ nums[i] ≤ n.
• O(n) time, no extra space (beyond output).

Constraints

• 1 <= nums.length <= 10^5.
• 1 <= nums[i] <= nums.length.

Examples to Get Us Started

• Input: nums = [4,3,2,7,8,2,3,1]
• Output: [5,6] (5 and 6 missing).
• Input: nums = [1,1]
• Output: [2] (2 missing).
• Input: nums = [1]
• Output: [] (Nothing missing).

Understanding the Problem: Tracking the Absentees

To solve LeetCode 448: Find All Numbers Disappeared in an Array in Python, we need to identify which numbers from 1 to n are absent, given that some appear twice. A naive approach—counting frequencies in a hash map—works but uses O(n) space, breaking the problem’s rule. The key insight? Numbers align with indices (1 to n, indices 0 to n-1), so we can mark presence in-place. We’ll explore:

• Best Solution (In-Place Marking): O(n) time, O(1) space—ingenious and efficient.
• Alternative Solution (Hash Set): O(n) time, O(n) space—simple but space-heavy.

Let’s dive into the in-place marking solution—it’s the roll-call trick we need.

Best Solution: In-Place Marking with Index Manipulation

Why This Is the Best Solution

The in-place marking approach is the top choice because it’s O(n) time and O(1) space (excluding output), perfectly meeting the problem’s constraints. It uses the array itself as a marker by negating values at indices corresponding to each number’s value, then identifies unmarked (positive) spots as missing. It’s like checking off students on the list itself, spotting who’s absent by the unchecked boxes—clever and compact!

How It Works

Here’s the strategy:

• Step 1: Iterate through nums:
• For each num, mark its corresponding index (abs(num) - 1) by negating the value there.
• Step 2: Iterate again:
• If nums[i] > 0, then i+1 is missing (never marked).
• Step 3: Return the list of missing numbers.
• Why It Works:
• Each number maps to a unique index.
• Negating marks presence without extra space.
• Positive values reveal absentees.

Step-by-Step Example

Example: nums = [4,3,2,7,8,2,3,1]

• Initial: [4, 3, 2, 7, 8, 2, 3, 1].
• Marking Pass:
• 4: index 3, [4, 3, 2, -7, 8, 2, 3, 1].
• 3: index 2, [4, 3, -2, -7, 8, 2, 3, 1].
• 2: index 1, [4, -3, -2, -7, 8, 2, 3, 1].
• 7: index 6, [4, -3, -2, -7, 8, 2, -3, 1].
• 8: index 7, [4, -3, -2, -7, 8, 2, -3, -1].
• 2: index 1 (already -3), no change.
• 3: index 2 (already -2), no change.
• 1: index 0, [-4, -3, -2, -7, 8, 2, -3, -1].
• Find Missing:
• Index 4: 8 > 0 → 5 missing.
• Index 5: 2 > 0 → 6 missing.
• Result: [5, 6].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        # Step 1: Mark presence by negating
        for num in nums:
            index = abs(num) - 1
            if nums[index] > 0:
                nums[index] = -nums[index]

        # Step 2: Find missing numbers
        result = []
        for i in range(len(nums)):
            if nums[i] > 0:
                result.append(i + 1)

        return result

• Line 4-6: First pass:
• Index = abs(num) - 1 (1-based to 0-based).
• Negate if positive (mark first visit).
• Line 9-12: Second pass:
• If nums[i] > 0, i+1 was never marked, add to result.
• Line 14: Return missing numbers.
• Time Complexity: O(n)—two passes.
• Space Complexity: O(1)—only output space.

It’s like a roll-call check-off right on the list!

Alternative Solution: Hash Set Approach

Why an Alternative Approach?

The hash set method builds a set of seen numbers—O(n) time, O(n) space—then checks 1 to n for absentees. It’s intuitive, like keeping a separate attendance sheet, but uses extra space, breaking the O(1) rule. Great for clarity or when space isn’t a constraint!

How It Works

• Step 1: Create a set from nums.
• Step 2: Check each number from 1 to n:
• If not in set, add to result.
• Step 3: Return missing numbers.

Step-by-Step Example

Example: nums = [4,3,2,7,8,2,3,1]

• Set: {1, 2, 3, 4, 7, 8}.
• Check 1 to 8:
• 1: present, 2: present, 3: present, 4: present.
• 5: missing, 6: missing.
• 7: present, 8: present.
• Result: [5, 6].

Code for Hash Set Approach

Copy codeclass Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        # Build set of present numbers
        num_set = set(nums)
        result = []

        # Check 1 to n
        for i in range(1, len(nums) + 1):
            if i not in num_set:
                result.append(i)

        return result

• Line 4: Create set from nums.
• Line 7-9: Check each number, add missing ones.
• Time Complexity: O(n)—set creation and loop.
• Space Complexity: O(n)—hash set.

It’s a straightforward absentee tracker!

Comparing the Two Solutions

• In-Place Marking (Best):
• Pros: O(n), O(1) space, meets constraints.
• Cons: Modifies input.
• Hash Set (Alternative):
• Pros: O(n), easy to understand.
• Cons: O(n) space, breaks rules.

In-place wins for efficiency.

Edge Cases and More Examples

• Input: [1] → [].
• Input: [2,2] → [1].
• Input: [1,2,3] → [].

Both handle these well.

Complexity Recap

• In-Place: Time O(n), Space O(1).
• Hash Set: Time O(n), Space O(n).

In-place is the champ.

Key Takeaways

• In-Place: Mark with indices.
• Hash Set: Track with a set.
• Python Tip: Arrays can double as maps—see [Python Basics](/python/basics).

Final Thoughts: Find Those Absentees

LeetCode 448: Find All Numbers Disappeared in an Array in Python is a clever array puzzle. In-place marking is your stealthy roll-call tool, while hash sets offer a clear backup. Want more array challenges? Try LeetCode 442: Find All Duplicates in an Array or LeetCode 287: Find the Duplicate Number. Ready to track some missing numbers? Head to Solve LeetCode 448 on LeetCode and take attendance today—your coding skills are present and accounted for!