Find All Numbers Disappeared in an Array

The problem is asking us to find all the numbers that are missing from the given array nums. The numbers in the array are in the range from 1 to ( n ), where ( n ) is the length of the array.

A simple approach to this problem is to use a set to track the numbers we’ve seen, and then iterate from 1 to ( n ) to find the missing numbers. However, since the constraints specify that we must not use extra space, we’ll use another method to solve the problem.

Here’s a step-by-step guide to the algorithm:

1. Mark Seen Numbers: Iterate through the array and mark the value at the index corresponding to each number as negative. This will allow us to identify which numbers were present in the original array.
2. Identify Missing Numbers: Iterate through the array again and identify the indexes where the values are positive. These indexes correspond to the missing numbers.

Here’s the code implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        # Step 1: Mark the numbers that appear in the array
        for num in nums:
            index = abs(num) - 1
            nums[index] = -abs(nums[index])

        # Step 2: Identify the missing numbers
        missing_numbers = [i + 1 for i in range(len(nums)) if nums[i] > 0]

        return missing_numbers

Example Explanation:

• For nums = [4,3,2,7,8,2,3,1], the output will be [5,6], as 5 and 6 are the missing numbers in the range from 1 to 8.
• For nums = [1,1], the output will be [2], as 2 is the missing number in the range from 1 to 2.

The time complexity of this solution is ( O(n) ), and the space complexity is ( O(1) ), as we are using the input array itself to track the numbers we’ve seen and not using any additional data structures.

Identifying Problem Isomorphism

“Find All Numbers Disappeared in an Array” can be mapped to “First Missing Positive”.

“Find All Numbers Disappeared in an Array” asks for all the numbers that don’t appear in the given array, which should have contained all numbers from 1 to n.

“First Missing Positive” is about finding the smallest positive number that doesn’t appear in the given array.

Both problems require the concept of checking the presence of certain elements in an array and are about missing numbers. However, the difference is that “Find All Numbers Disappeared in an Array” looks for all such missing numbers, whereas “First Missing Positive” is interested only in the smallest one.

So, both problems are similar in terms of concept, but “Find All Numbers Disappeared in an Array” is a more complex because it requires handling multiple missing numbers.

1
2
3
4
5
6

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for n in nums:
            a = abs(n) - 1
            if nums[a] > 0: nums[a] *= -1
        return [i+1 for i in range(len(nums)) if nums[i] > 0]

0 1 2 3 4 5 6 7 [4, 3, 2, 7, 8, 2, 3, 1] [4, 3, 2, -7, 8, 2, 3, 1] 4 [4, 3, -2, -7, 8, 2, 3, 1] 3 [4, -3, -2, -7, 8, 2, 3, 1] -2 [4, -3, -2, -7, 8, 2, -3, 1] 7 [4, -3, -2, -7, 8, 2, -3, -1] 8 [4, -3, -2, -7, 8, 2, -3, -1] 2 [4, -3, -2, -7, 8, 2, -3, -1] -3 [-4, -3, -2, -7, 8, 2, -3, -1] -1 0. 1. 2. 3. 4. 5. 6. 7

[7,3,2,4,8,2,3,1] [3,3,2,4,8,2,7,1] [3,2,3,4,8,2,7,1] [3,2,3,4,1,2,7,8] [1,2,3,4,3,2,7,8] [1,2,3,4,3,2,7,8]

T: O(n+n) : O(n) It is a bit more than that. Loops are not nested. Two loops. S: O(1)

T: O(n) S: O(1)

1. Numbers are between [1,n] inclusive
2. Use number - 1 as the index and put that number is that location Swap? or keep in a local variable
3. Whenever we find the number appropriate for that index we put that number in that location

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

# @param {Integer[]} nums
# @return {Integer[]}

def find_disappeared_numbers(nums)
    output = []

    for i in (0..nums.size-1)
       new_index = nums[i].abs - 1 

       if nums[new_index] > 0
          nums[new_index] *= -1 
       end
    end

    for i in (0..nums.size-1)
       if nums[i] > 0
          output << i + 1
       end
    end

    return output
end

Problem Classification

1. Array Manipulation: This problem deals with the manipulation of an array of integers. We need to traverse, compare, and return a new array based on the existing one.

2. Number Theory: As the problem requires understanding of numbers and ranges, it involves basic number theory.

3. Set Difference: The problem is essentially asking for a set difference between the range of numbers from 1 to n and the given array, which is a concept from Set Theory.

4. Searching: This problem involves searching for missing elements in the array, which is a common problem in algorithmic problem solving.

This is a problem of “In-place Array Manipulation” due to a commonly used technique that solves the problem in O(1) space complexity.

Language Agnostic Coding Drills

Here is the problem breakdown in the smallest units of learning, the solution’s components:

1. Understanding Absolute Value: Understand the concept of absolute value and how it is used in code. The absolute value of a number disregards the sign of the number and considers only the magnitude.

2. Indexing in Arrays: Grasp the knowledge of how to access elements in an array using their indices. Understand the concept of zero-indexing in programming.

3. In-Place Modification: Learn how to modify an array in-place. In this context, “in-place” means without creating a new array or list.

4. Conditional Statements: Understand the use of if statements to perform different actions based on different conditions.

5. List Comprehension: Understand the concept of list comprehension in Python, which provides a concise way to create lists based on existing lists.

The approach to solving the problem is as follows:

1. The idea is to leverage the fact that the elements are between 1 and the size of the array. The algorithm loops through each number in the array and uses the absolute value of that number minus one as an index. The value at that index is then negated if it is positive.

2. After this process, the indices of the positive values in the array represent the numbers that are missing from the original array.

3. Using list comprehension, a new list is created that contains all numbers i (1-indexed) that correspond to positive values in the array.

Once these concepts are understood and drills are done on these individual parts, they can be combined to write the solution for the problem at hand.

Targeted Drills in Python

1. Understanding Absolute Value: You can experiment with the absolute value function in Python. Here’s a simple drill:

   1 2 3 4 5 6 7

   # Code to print absolute value def print_absolute(n): print(f"Absolute value of {n} is {abs(n)}") # Test the function print_absolute(-5) print_absolute(5)

2. Indexing in Arrays: Try creating a list and accessing its elements through indices.

   1 2 3 4 5 6 7

   # Code to test array indexing def test_indexing(arr): for i in range(len(arr)): print(f"Element at index {i} is {arr[i]}") # Test the function test_indexing([1, 2, 3, 4, 5])

3. In-Place Modification: Practice modifying an array in place by negating all its elements.

   1 2 3 4 5 6 7 8

   # Code to negate array elements def negate_array(arr): for i in range(len(arr)): arr[i] *= -1 return arr # Test the function print(negate_array([1, 2, 3, 4, 5]))

4. Conditional Statements: Implement a function that prints whether each element in an array is positive or negative.

   1 2 3 4 5 6 7 8 9 10

   # Code to print if array elements are positive def print_positive_or_negative(arr): for num in arr: if num > 0: print(f"{num} is positive") else: print(f"{num} is negative") # Test the function print_positive_or_negative([1, -2, 3, -4, 5])

5. List Comprehension: Write a function that uses list comprehension to create a list of the squares of all numbers from 1 to n.

   1 2 3 4 5 6

   # Code to create list of squares def list_of_squares(n): return [i ** 2 for i in range(1, n+1)] # Test the function print(list_of_squares(5))

After practicing these drills separately, you should be well-prepared to understand and implement the final solution to the problem.