Find All Numbers Disappeared in an Array - LeetCode 448 Solution in python

Find All Numbers Disappeared in an Array easy

Problem Statement

Given an array nums of integers between 1 and n (inclusive), where n is the length of the array, find all the numbers that are missing from the array.

Example 1:

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

Example 2:

Input: nums = [1,1] Output: [2]

Steps:

Utilize the array as a hash table: We can leverage the fact that the numbers are in the range [1, n]. We'll use the array's indices to represent the numbers. If a number x is present in the array, we'll mark its corresponding index x - 1 as negative.
Iterate and mark: We iterate through the array. For each number num, we mark the element at index abs(num) - 1 as negative. We use abs(num) because we may already have negated the value.
Collect missing numbers: After the first iteration, any index that still holds a positive value indicates a missing number. We collect these indices and add 1 to each to obtain the missing numbers.

Explanation:

The core idea is to use the array itself to track the presence of numbers. By negating the value at the index corresponding to a number, we efficiently mark its presence. We avoid using extra space beyond the input array.

Consider nums = [4,3,2,7,8,2,3,1].

Iteration 1 (num = 4): nums[3] (index 3) becomes negative. nums becomes [4, 3, 2, -7, 8, 2, 3, 1].
Iteration 2 (num = 3): nums[2] becomes negative. nums becomes [4, 3, -2, -7, 8, 2, 3, 1].
...and so on.

After the loop, positive values indicate missing numbers. The indices are then adjusted to get the actual missing numbers.

Code:

function findDisappearedNumbers(nums: number[]): number[] {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        const index = Math.abs(nums[i]) - 1; //adjust index to be 0-based
        if (nums[index] > 0) {
            nums[index] = -nums[index]; // Mark the number as present
        }
    }

    const missingNumbers: number[] = [];
    for (let i = 0; i < n; i++) {
        if (nums[i] > 0) {
            missingNumbers.push(i + 1); //Adjust index back to 1-based
        }
    }

    return missingNumbers;
};

Complexity:

Time Complexity: O(n), where n is the length of the input array. We iterate through the array twice.
Space Complexity: O(1). We modify the input array in-place, using constant extra space. The missingNumbers array's size is at most n, but this is not considered extra space because the problem implicitly allows modifying the input array.