448. Find All Numbers Disappeared in an Array

EasyArrayHash Table

Problem Description

The given problem describes a scenario where we have an array nums containing n integers. Each integer is within the range from 1 to n. The goal is to find all the numbers that are missing from the array. A number is missing if it is within the given range but does not appear in nums. The task is to return an array of all such missing integers.

Intuition

To efficiently find the missing numbers without using extra space, we can harness the fact that the integers in nums are in the range [1, n] and use the index as a way to flag whether a number is present. By traversing the nums array, for each value x we encounter, we can mark that x is present by flipping the sign of the element at index x-1. Note that we use abs(x) - 1 because the values in nums are 1-based, and Python uses 0-based indexing. Moreover, to ensure we don't flip the sign back if we encounter the same number twice, we only flip the sign if it's positive.

Once we've completed marking the presence of numbers, we can make a second pass through the nums array. This time, for each index i, if nums[i] is positive, it indicates that the number i+1 (since i is 0-based) was never marked and thus is missing from nums. We collect all these missing numbers and return them in the final array.

This approach works in-place, without the need for additional memory for tracking the presence of numbers, and runs in linear time since we make two passes through the array.

Solution Approach

The solution utilizes a clever trick that takes advantage of the fact that the array nums is mutable and that all elements are initially positive. This trick uses the sign of each element to indicate whether a number corresponding to an index has been encountered. Here is a step-by-step explanation:

Loop Through nums: We iterate over each element x in the array nums.
Calculate Index: For each number x, we compute the index i = abs(x) - 1. The abs function ensures that we are always working with a positive index, which is important since we might have previously negated some elements in nums.
Negate Elements: We negate the number at index i in nums if it's positive (if nums[i] > 0). Negating an element marks that the number i + 1 is present in the array. If the element at index i is already negative, we do nothing since this implies the presence of i + 1 has already been recorded.
Identify Missing Numbers: After negating elements in step 3, numbers corresponding to indices with positive values in nums are the ones missing from the array. Thus, we create a list of such numbers by checking for positive values in nums and adjusting the index i to the actual missing number i + 1.

The algorithm employs no additional data structures for tracking purposes, so the space complexity remains constant, i.e., O(1) (not counting the output array). The time complexity is O(n) because the array is traversed twice: once for marking presence and once for identifying missing numbers. The in-place marking is a pattern that exploits the known range of input values to use the array itself as a direct-access data structure for tracking the presence of numbers.

In summary, the algorithm leverages in-place array manipulation to solve the problem efficiently.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose our nums array is [4, 3, 2, 7, 8, 2, 3, 1], which has n = 8 numbers, and we are looking to find the missing numbers in the range from 1 to 8.

First Loop:
- We begin by traversing the array nums. The first number is 4. We calculate the index for 4, which is abs(4)-1 = 3. The number at index 3 is 7, and since it's positive, we negate it to mark that 4 is present.
- Continuing, we encounter 3, so abs(3)-1 = 2. We negate the number at index 2, which is now -2 (it was 2 before negating 7, but the value doesn't matter as we're using the absolute value).
- We repeat this process for each number, and our array looks like this after the first loop: [-4, -3, -2, -7, 8, 2, -3, -1]. Notably, the elements at indices 4 and 5 remain positive, signaling that the corresponding numbers 5 and 6 are missing.
Second Loop:
- In this pass, we look for indices with positive numbers. At index 4, the value is 8, which is positive, so we know that 5 is missing (4 + 1).
- Similarly, at index 5, the value is 2, which is positive, so 6 is missing (5 + 1).

The final output array containing all missing numbers is [5, 6], as these are the numbers not marked in the nums array. This example demonstrates how, by negating numbers and using the original array as a marker, we can efficiently identify missing elements with only two traversals of nums, achieving O(n) time complexity with constant O(1) space complexity, excluding the output array.

Solution Implementation

1class Solution:
2    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
3        # Iterate through each number in the input list
4        for number in nums:
5            # Use the absolute value to find the index (since we might have negative values due to marking)
6            index = abs(number) - 1
7          
8            # Mark the number at this index as visited by making it negative
9            # Only mark it if it is positive (to handle duplicates, ensure only marked once)
10            if nums[index] > 0:
11                nums[index] *= -1
12      
13        # After marking all numbers, the positive numbers' indices are the missing ones
14        # Iterate through the list, and for each positive number, the index + 1 is a missing number
15        missing_numbers = [i + 1 for i, x in enumerate(nums) if x > 0]
16      
17        return missing_numbers
18

1class Solution {
2  
3    /**
4     * Finds all the elements of [1, n] inclusive that do not appear in the array.
5     *
6     * @param nums Array of integers ranging from 1 to n, possibly containing duplicates.
7     * @return A list of integers that are missing from the array.
8     */
9    public List<Integer> findDisappearedNumbers(int[] nums) {
10        int n = nums.length;
11
12        // Iterate over each number in the array.
13        for (int num : nums) {
14            // Use absolute value in case nums[i] has been marked negative already.
15            int index = Math.abs(num) - 1;
16          
17            // Mark the number at index i as negative if it's not already.
18            if (nums[index] > 0) {
19                nums[index] = -nums[index];
20            }
21        }
22
23        // Create a list to hold the result of missing numbers.
24        List<Integer> missingNumbers = new ArrayList<>();
25
26        // Check for numbers that were not marked negative.
27        for (int i = 0; i < n; i++) {
28            // If the number is positive, the number (i + 1) is missing.
29            if (nums[i] > 0) {
30                missingNumbers.add(i + 1);
31            }
32        }
33
34        return missingNumbers;
35    }
36}
37

1class Solution {
2public:
3    vector<int> findDisappearedNumbers(vector<int>& nums) {
4        int size = nums.size(); // Get the size of the input vector
5      
6        // Iterate over all elements in the input vector
7        for (int& num : nums) {
8            int index = abs(num) - 1; // Calculate the index from the value
9          
10            // If the value at the calculated index is positive, negate it
11            // Negation marks that the number at 'index + 1' exists in the array
12            if (nums[index] > 0) {
13                nums[index] = -nums[index];
14            }
15        }
16      
17        vector<int> result; // Initialize an empty vector to store missing numbers
18      
19        // Iterate over the numbers from 1 to n and find which indices have positive values
20        for (int i = 0; i < size; ++i) {
21            // If the value at index 'i' is positive, it means 'i + 1' is missing
22            if (nums[i] > 0) {
23                result.push_back(i + 1); // Add the missing number to the result vector
24            }
25        }
26      
27        return result; // Return the vector of missing numbers
28    }
29};
30

1function findDisappearedNumbers(nums: number[]): number[] {
2    const size = nums.length; // The size of the input array 'nums'.
3    // Mark each number that appears in the array by negating the value at the index
4    // corresponding to that number.
5    for (const num of nums) {
6        const index = Math.abs(num) - 1; // Calculate the correct index.
7        // Negate the number at the index if it is positive.
8        if (nums[index] > 0) {
9            nums[index] = -nums[index];
10        }
11    }
12
13    // Initialize an array to hold the numbers that did not appear in 'nums'.
14    const missingNumbers: number[] = [];
15    // Traverse the array to find the indices that contain a positive number, which
16    // indicates that the number corresponding to that index did not appear in 'nums'.
17    for (let i = 0; i < size; i++) {
18        if (nums[i] > 0) {
19            missingNumbers.push(i + 1); // Add the missing number to the result array.
20        }
21    }
22
23    // Return the array containing all the missing numbers.
24    return missingNumbers;
25}
26

Time and Space Complexity

The time complexity of the provided code is O(n). This is because the code consists of a single loop that goes through the nums array with n elements exactly once, marking each number that has been seen by negating the value at the index corresponding to that number. The loop to create the output list also runs for n elements, so the entire operation is linear.

The space complexity of the code is O(1), as it only uses constant extra space. The input list is modified in place to keep track of which numbers have been seen. The list of disappeared numbers is the only additional space used, and it's the output of the function, which typically isn't counted towards space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know