Find All Numbers Disappeared in an Array

LeetCode 448: Find All Numbers Disappeared in an Array Solution & Explanation

Problem Overview

TL;DR: By utilizing the Cyclic Sort technique, we arrange numbers to their corresponding indices (e.g., placing value 3 at index 2) in-place, allowing us to identify missing numbers by checking which indices do not match their expected values.

The "Find All Numbers Disappeared in an Array" problem asks us to identify missing integers from a sequence. We are given an array nums containing n integers where each integer is within the range [1, n]. Some numbers appear twice, while others appear once. Our goal is to return a list of all integers in the range [1, n] that are not present in nums.

This is a classic interview question that tests the ability to manipulate arrays in-place to achieve optimal space complexity. Specifically, the LeetCode 448 solution requires identifying these numbers without using extra space for a hash set or boolean array.

Brute Force Approach for Find All Numbers Disappeared in an Array

The most intuitive way to solve this problem is to track the frequency or presence of each number using an auxiliary data structure.

1. Create a Hash Set or a boolean array of size n + 1.
2. Iterate through the input array nums and mark each number as "seen" in our data structure.
3. Iterate through the range of numbers from 1 to n.
4. If a number is not marked as "seen", add it to the result list.

Pseudo-code

function findDisappearedNumbers(nums):
    seen = new HashSet()
    for num in nums:
        seen.add(num)
    
    missing = []
    for i from 1 to n:
        if i not in seen:
            missing.append(i)
            
    return missing

Analysis of Brute Force

• Time Complexity: $O(n)$. We iterate through the array once and the range 1 to n once.
• Space Complexity: $O(n)$. We require a Hash Set or boolean array to store the presence of up to n elements.

Why it fails: While this solution is correct and runs in linear time, it violates the follow-up constraint of the problem, which asks for $O(1)$ extra space (excluding the returned list). To satisfy the space constraint, we must utilize the input array itself to track state.

Algorithm Strategy: Array - Cyclic Sort

1. Iterate and Swap: Traverse the array from the beginning. For each element, determine its correct index (value - 1).
2. Cyclic Placement: If the element is not at its correct index AND the element at the target index is not already the correct value, swap them.
3. Stay or Advance: If a swap occurs, do not advance the iterator; check the new value that was swapped into the current position. If no swap is needed (either the element is correct or the target is a duplicate), advance the iterator.
4. Identify Missing: After the single pass of sorting, iterate through the array again. Any index i where nums[i] != i + 1 indicates that the number i + 1 is missing from the array.

Execution Flow

Let's trace nums = [4, 3, 2, 7, 8, 2, 3, 1].

Phase 1: Cyclic Sort

1. i = 0, nums[0] = 4. Target index is 3. nums[3] is 7. Swap.
   • Array: [7, 3, 2, 4, 8, 2, 3, 1]
2. i = 0, nums[0] = 7. Target index is 6. nums[6] is 3. Swap.
   • Array: [3, 3, 2, 4, 8, 2, 7, 1]
3. i = 0, nums[0] = 3. Target index is 2. nums[2] is 2. Swap.
   • Array: [2, 3, 3, 4, 8, 2, 7, 1]
4. i = 0, nums[0] = 2. Target index is 1. nums[1] is 3. Swap.
   • Array: [3, 2, 3, 4, 8, 2, 7, 1]
5. i = 0, nums[0] = 3. Target index is 2. nums[2] is 3 (Duplicate found). Advance i.
6. i = 1, nums[1] = 2. Correct position. Advance i.
7. ... (Process continues until array is sorted as best as possible)
   • Final Sorted State: [1, 2, 3, 4, 3, 2, 7, 8]

Phase 2: Identification

1. Index 0: nums[0] (1) == 0 + 1. Correct.
2. Index 1: nums[1] (2) == 1 + 1. Correct.
3. Index 2: nums[2] (3) == 2 + 1. Correct.
4. Index 3: nums[3] (4) == 3 + 1. Correct.
5. Index 4: nums[4] (3) != 4 + 1. Missing 5.
6. Index 5: nums[5] (2) != 5 + 1. Missing 6.
7. Index 6: nums[6] (7) == 6 + 1. Correct.
8. Index 7: nums[7] (8) == 7 + 1. Correct.

Result: [5, 6]

Proof of Correctness

The correctness relies on the Pigeonhole Principle and the defined range [1, n].

1. Placement Guarantee: The swapping logic ensures that if a value x exists in the input, it is placed at index x-1. The condition nums[nums[i] - 1] != nums[i] ensures we only stop swapping when the target position holds the correct value.
2. Duplicate Handling: If x appears twice, the first instance fills index x-1. The second instance remains in a "wrong" slot because the "right" slot is already occupied by an identical value.
3. Missing Value Detection: Consequently, if index i does not hold value i+1, it implies i+1 was never swapped into its position. Since the algorithm guarantees placement if the value exists, i+1 must be missing.

Pattern Reuse Notes

The Array - Cyclic Sort pattern is highly specific to problems involving arrays containing numbers in a contiguous range (like 1 to n or 0 to n).

• LeetCode 41: First Missing Positive - Uses Cyclic Sort to place positives in order, then finds the first index mismatch.
• LeetCode 268: Missing Number - Very similar to 448, but the range is 0 to n and only one number is missing.
• LeetCode 287: Find the Duplicate Number - Can use Cyclic Sort to place numbers; the duplicate will inevitably try to occupy an already filled slot.
• LeetCode 442: Find All Duplicates in an Array - Identical logic to 448, but instead of collecting indices where values are missing, you collect the values that end up in the wrong indices.

Reference Implementation

C++ Solution for LeetCode 448

1class Solution {
2public:
3    vector<int> findDisappearedNumbers(vector<int>& nums) {
4        int n = nums.size();
5        int i = 0;
6        
7        // Cyclic Sort Phase
8        while (i < n) {
9            int correctIdx = nums[i] - 1;
10            // If the current number is not at the correct index
11            // AND the correct index doesn't already have the correct number
12            if (nums[i] != nums[correctIdx]) {
13                swap(nums[i], nums[correctIdx]);
14            } else {
15                i++;
16            }
17        }
18        
19        // Identification Phase
20        vector<int> result;
21        for (int j = 0; j < n; j++) {
22            // If the number at index j is not j + 1, then j + 1 is missing
23            if (nums[j] != j + 1) {
24                result.push_back(j + 1);
25            }
26        }
27        
28        return result;
29    }
30};

Java Solution for LeetCode 448

1class Solution {
2    public List<Integer> findDisappearedNumbers(int[] nums) {
3        int i = 0;
4        int n = nums.length;
5        
6        // Cyclic Sort Phase
7        while (i < n) {
8            int correctIdx = nums[i] - 1;
9            // Check if element is in correct position or if target is duplicate
10            if (nums[i] != nums[correctIdx]) {
11                // Swap nums[i] and nums[correctIdx]
12                int temp = nums[i];
13                nums[i] = nums[correctIdx];
14                nums[correctIdx] = temp;
15            } else {
16                i++;
17            }
18        }
19        
20        // Identification Phase
21        List<Integer> result = new ArrayList<>();
22        for (int j = 0; j < n; j++) {
23            if (nums[j] != j + 1) {
24                result.add(j + 1);
25            }
26        }
27        
28        return result;
29    }
30}

Python Solution for LeetCode 448

1class Solution:
2    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
3        i = 0
4        n = len(nums)
5        
6        # Cyclic Sort Phase
7        while i < n:
8            correct_idx = nums[i] - 1
9            # If current value is not in correct position
10            # and the target position doesn't already contain the correct value
11            if nums[i] != nums[correct_idx]:
12                # Swap
13                nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
14            else:
15                i += 1
16        
17        # Identification Phase
18        result = []
19        for j in range(n):
20            if nums[j] != j + 1:
21                result.append(j + 1)
22                
23        return result