Find All Numbers Disappeared In An Array

                                            
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> result;
        for(int i=0; i<nums.size(); i++) {
            int index = abs(nums[i]) - 1;
            if(nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        for(int i=0; i<nums.size(); i++) {
            if(nums[i] > 0) {
                result.push_back(i+1);
            }
        }
        return result;
    }
};

                                            
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                result.add(i + 1);
            }
        }
        
        return result;
    }
}

                                            
class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        for num in nums:
            index = abs(num) - 1
            if nums[index] > 0:
                nums[index] = -nums[index]
        
        result = []
        for i in range(n):
            if nums[i] > 0:
                result.append(i+1)
        
        return result

                                            
/**
 * Note: The returned array must be malloced, assume caller 
calls free().
 */
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
    int* res = (int*)malloc(sizeof(int) * numsSize);
    *returnSize = 0;
    
    for(int i = 0; i < numsSize; i++){
        int index = abs(nums[i]) - 1;
        if(nums[index] > 0){
            nums[index] = -nums[index];
        }
    }
    
    for(int i = 0; i < numsSize; i++){
        if(nums[i] > 0){
            res[(*returnSize)++] = i + 1;
        }
    }
    
    return res;
}

                                            
public class Solution {
    public IList<int> FindDisappearedNumbers(int[] nums) {
        IList<int> result = new List<int>();

        for (int i = 0; i < nums.Length; i++) {
            int index = Math.Abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }

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

        return result;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        const index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.push(i + 1);
        }
    }
    return result;
};

                                            
function findDisappearedNumbers(nums: number[]): number[] {
    const result: number[] = [];
    
    for (let i = 0; i < nums.length; i++) {
        const newIndex = Math.abs(nums[i]) - 1;
        if (nums[newIndex] > 0) {
            nums[newIndex] *= -1;
        }
    }
    
    for (let i = 1; i <= nums.length; i++) {
        if (nums[i - 1] > 0) {
            result.push(i);
        }
    }
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function findDisappearedNumbers($nums) {
        $result = [];
        $n = count($nums);
        $map = array_fill(1, $n, false);
        
        foreach ($nums as $num) {
            $map[$num] = true;
        }
        
        foreach ($map as $key => $val) {
            if (!$val) {
                $result[] = $key;
            }
        }
        
        return $result;
    }
}

                                            
class Solution {
    func findDisappearedNumbers(_ nums: [Int]) -> [Int] {
        var nums = nums
        var result = [Int]()
        
        for num in nums {
            let index = abs(num) - 1
            if nums[index] > 0 {
                nums[index] *= -1
            }
        }
        
        for i in 0..<nums.count {
            if nums[i] > 0 {
                result.append(i + 1)
            }
        }
        
        return result
    }
}

                                            
class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        val result = mutableListOf<Int>()
        val n = nums.size
        val numSet = HashSet<Int>()
        
        for (num in nums) {
            numSet.add(num)
        }
        
        for (i in 1..n) {
            if (!numSet.contains(i)) {
                result.add(i)
            }
        }
        
        return result
    }
}

                                            
class Solution {
  List<int> findDisappearedNumbers(List<int> nums) {
    List<int> result = [];
    
    for (int i = 0; i < nums.length; i++) {
      int index = (nums[i].abs()) - 1;
      if (nums[index] > 0) {
        nums[index] = -nums[index];
      }
    }
    
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] > 0) {
        result.add(i + 1);
      }
    }
    
    return result;
  }
}

                                            
func findDisappearedNumbers(nums []int) []int {
    result := []int{}
    
    for _, num := range nums {
        index := abs(num) - 1
        if nums[index] > 0 {
            nums[index] = -nums[index]
        }
    }
    
    for i, num := range nums {
        if num > 0 {
            result = append(result, i+1)
        }
    }
    
    return result
}

func abs(num int) int {
    if num < 0 {
        return -num
    }
    return num
}

                                            
# @param {Integer[]} nums
# @return {Integer[]}
def find_disappeared_numbers(nums)
    result = []
    n = nums.length
    nums.each { |num| nums[(num - 1) % n] += n }
    nums.each_with_index { |num, index| result << index + 1 if num <= n }
    result
end

                                            
object Solution {
    def findDisappearedNumbers(nums: Array[Int]): List[Int] = {
        val n = nums.length
        val numSet = nums.toSet
        (1 to n).filter(!numSet.contains(_)).toList
    }
}

                                            
impl Solution {
    pub fn find_disappeared_numbers(nums: Vec<i32>) -> Vec<i32> {
        let mut nums = nums;
        let n = nums.len();

        for i in 0..n {
            let idx = (nums[i].abs() - 1) as usize;
            if nums[idx] > 0 {
                nums[idx] = -nums[idx];
            }
        }

        let mut result = Vec::new();
        for i in 0..n {
            if nums[i] > 0 {
                result.push(i as i32 + 1);
            }
        }

        result
    }
}

                                            
(define/contract (find-disappeared-numbers nums)
  (-> (listof exact-integer?) (listof exact-integer?))
  (define n (+ 1 (length nums)))
  (define present (make-vector n #f))
  (for ([num nums]) (vector-set! present num #t))
  (define disappeared '())
  (for ([i (in-range 1 n)]) (unless (vector-ref present i) (set! disappeared (cons i disappeared))))
  disappeared
)

                                            
-spec find_disappeared_numbers(Nums :: [integer()]) -> 
[integer()].
find_disappeared_numbers(Nums) ->
    lists:seq(1, length(Nums)) -- Nums.

                                            
defmodule Solution do
  @spec find_disappeared_numbers(nums :: [integer]) :: [integer]
  def find_disappeared_numbers(nums) do
    1..length(nums)
    |> Enum.reject(&Enum.member?(nums, &1))
  end
end

To solve this coding challenge, we need to identify and return all the numbers in the range [1, n] that are missing from the given array

nums

. The array

nums

has a length of

n

, and every element in

nums

is an integer within the range [1, n]. We need to find a way to achieve this with O(n) runtime without using extra space, although the returned list does not count as extra space per the problem constraints.

Explanation

Here's a detailed breakdown of how we can approach this problem:

Understand the Problem Constraints :

We have an array
nums

of length
n

.
Every element in
nums

lies between 1 and
n

(inclusive).

Objective :

Identify all the integers from 1 to
n

that are not present in the array
nums

.
Return these missing integers in a list.

Optimal Strategy :

We need to achieve this in O(n) runtime and with constant extra space.
A classic approach to achieve O(n) runtime involves modifying the original array in place to mark the presence of elements.

Marking Presence :

For each element in the array, the index corresponding to the value (reduced by 1) can be used to mark its presence.
To avoid using extra space, we can mark an element as seen by making the value at the corresponding index negative (only if it’s not already negative).
This marks the index
i

as visited meaning value
i+1

is present in the array.

Identifying Missing Numbers :

After marking all present elements, any index
i

that has a positive value indicates that the number
i+1

is missing from the array.

Implementation Steps :

Iterate over each element in the array and use its absolute value to determine the index to mark as visited.
Iterate over the array again to collect all indices that have positive values; these indices correspond to missing numbers.

Pseudocode with Comments

                                            
# Step 1: Define the function to find disappeared numbers
function findDisappearedNumbers(nums):
# Get the length of the input array
array_length = length(nums)

# Step 2: Mark presence of each number
for each element in nums:
# Calculate the corresponding index
corresponding_index = absolute_value(element) - 1

# Mark the presence by making the value at corresponding_index negative
if nums[corresponding_index] > 0:
nums[corresponding_index] = -nums[corresponding_index]

# Step 3: Collect the missing numbers
missing_numbers = []
for i in range(array_length):
# If the value at index i is positive, it means number i+1 is missing
if nums[i] > 0:
missing_numbers.append(i + 1)

# Step 4: Return the list of missing numbers
return missing_numbers

Detailed Steps in Pseudocode

Initialization :

Define a function
findDisappearedNumbers

that takes an array
nums

as input.
Calculate the length of
nums

and store it in
array_length

.

Marking Phase :

Iterate over each element in
nums

.
For each element, compute
corresponding_index

as
abs(element) - 1

.
Check if
nums[corresponding_index]

is positive.
If it is positive, negate the value at
nums[corresponding_index]

to mark it as visited.

Collection Phase :

Initialize an empty list
missing_numbers

to collect results.
Iterate over the range from 0 to
array_length - 1

.
For each index
i

, check if
nums[i]

is positive.
If
nums[i]

is positive, append
i + 1

to
missing_numbers

.

Final Output :

Return the
missing_numbers

list containing all the integers from 1 to
n

that are not present in
nums

.

This approach ensures that we modify the input array in place and collect the results efficiently, respecting both the time complexity and space constraints mentioned in the problem.