Find All Numbers Disappeared in an Array

🏠 ⬅️ ➡️

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

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

Example 2:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 9
    integer, dimension(n) :: nums
    integer, dimension(:), allocatable :: result
    integer :: i

    ! Example 1
    nums = [4, 3, 2, 7, 8, 2, 3, 1]
    call solve(nums, result)
    write (*, '(*(I0, 1X))') result

    ! Example 2
    nums = [1, 1]
    call solve(nums, result)
    write (*, '(*(I0, 1X))') result

contains

    subroutine solve(nums, result)
        implicit none
        integer, intent(in) :: nums(:)
        integer, allocatable, intent(out) :: result(:)
        integer :: i, j

        allocate (result(n))

        do i = 1, n
            result(i) = i
        end do

        do i = 1, size(nums)
            j = nums(i)
            if (j /= i) then
                result(i) = result(j)
                result(j) = i
            end if
        end do

        do i = 1, n
            if (result(i) /= i) then
                result(i) = 0
            end if
        end do

    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module missing_numbers

implicit none

contains

function find_missing_numbers(nums) result(missing_numbers)

! This function takes an array of integers `nums` and returns an array of all the
! integers in the range [1, n] that do not appear in `nums`.

! The function should run in O(n) time and use constant extra space.

! The input array `nums` is guaranteed to be in the range [1, n], where n is the
! length of the array.

! The output array should be sorted in ascending order.

! The function should return an empty array if there are no missing numbers.

integer, intent(in) :: nums(:)
integer :: missing_numbers(size(nums))
integer :: i, j, n

! Initialize the output array with the default value.
missing_numbers = -1

! Find the length of the input array.
n = size(nums)

! Loop through the input array and mark the elements as present.
do i = 1, n
    j = nums(i)
    if (j > 0) then
        missing_numbers(j) = 0
    end if
end do

! Find the first missing number.
do i = 1, n
    if (missing_numbers(i) == 1) then
        exit
    end if
end do

! If there are no missing numbers, return an empty array.
if (i > n) then
    return
end if

! Loop through the output array and find the remaining missing numbers.
do j = i, n
    if (missing_numbers(j) == 1) then
        exit
    end if
end do

! Return the array of missing numbers.
missing_numbers(i:j) = [i, (i+1):j]

end function find_missing_numbers

end module missing_numbers

program test_find_missing_numbers

use missing_numbers, only : find_missing_numbers
implicit none

! Test case 1:
call test(find_missing_numbers([4,3,2,7,8,2,3,1]), [5,6])

! Test case 2:
call test(find_missing_numbers([1,1]), [2])

! Test case 3:
call test(find_missing_numbers([1,2,3,4,5,6,7,8,9]), [])

contains

subroutine test(actual, expected)

integer, intent(in) :: actual(:), expected(:)
integer :: i

! Check if the output array is the same size as the expected array.
if (size(actual) /= size(expected)) then
    write (*,*) "Test failed."
    stop
end if

! Check if each element in the output array is equal to the corresponding element
! in the expected array.
do i = 1, size(actual)
    if (actual(i) /= expected(i)) then
        write (*,*) "Test failed."
        stop
    end if
end do

write (*,*) "Test passed."

end subroutine test

end program test_find_missing_numbers
🌐 Data from online sources 
def find_disappeared_numbers(nums):
    result = []

    for num in nums:
        index = abs(num) - 1
        nums[index] = -abs(nums[index])

    for i, num in enumerate(nums):
        if num > 0:
            result.append(i + 1)

    return result

The algorithm works as follows:

  1. Iterate through the input array.
  2. For each value nums[i], find its index by subtracting 1 (index = abs(nums[i]) - 1). This is because the integers in the range are 1 to n, and indices are 0-indexed.
  3. Negate the value at this index (nums[index] = -abs(nums[index])). This marks the value as "found".
  4. Iterate through the modified array.
  5. If a value is positive, it means the integer corresponding to that index hasn't been found. Add it to the result array.

This algorithm has a time complexity of O(n) and doesn't use any additional space other than the result array.

🌐 Data from online sources 
#include <vector>
using namespace std;

vector<int> findDisappearedNumbers(vector<int> &nums) {
    vector<int> result;

    for (int i = 0; i < nums.size(); ++i) {
        int index = abs(nums[i]) - 1;
        nums[index] = -abs(nums[index]);
    }

    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] > 0) {
            result.push_back(i + 1);
        }
    }

    return result;
}

The algorithm works as follows:

  1. Iterate through the input array.
  2. For each value nums[i], find its index by subtracting 1 (index = abs(nums[i]) - 1). This is because the integers in the range are 1 to n, and indices are 0-indexed.
  3. Negate the value at this index (nums[index] = -abs(nums[index])). This marks the value as "found".
  4. Iterate through the modified array.
  5. If a value is positive, it means the integer corresponding to that index hasn't been found. Add it to the result array.

This algorithm has a time complexity of O(n) and doesn't use any additional space other than the result array.