Find All Numbers Disappeared in an Array Leetcode Solution

Table of Contents

Problem Statement

In this problem, we are given an array of integers. It contains elements ranging from 1 to N, where N = size of the array. However, there are some elements that have disappeared and some duplicates are present in their place. Our goal is to return an array of all such disappeared integers.

Example

Array = {1 , 2 , 5 , 6 , 2 , 5}

3 4

Find All Numbers Disappeared in an Array Leetcode Solution

Array = {1 , 2 , 3 , 4}

Approach(Using HashSet)

We can mark every element in the array and then loop in the range: [1, N] to check which elements have disappeared or are missing in the array. We use a hash set to store whether an integer has been marked or not.

Algorithm

Initialize a hash set mark[Integer] to store elements that are present.
For every element i in the array:
- Add i to mark
Initialize a List/vector result to store missing elements in the array
For every element i in the range: [1, N]:
- If i is not present in mark:
  - Add it to result
Return result
Print the result

Implementation of Find All Numbers Disappeared in an Array Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    unordered_set <int> mark;
    for(int &i : a)
        mark.insert(i);
    int N = a.size();
    vector <int> result;
    for(int i = 1 ; i <= N ; i++)
        if(mark.find(i) == mark.end())
            result.emplace_back(i);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

Java Program

import java.util.*;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashSet <Integer> mark = new HashSet <Integer>();
        for(int i : a)
            mark.add(i);

        for(int i = 1 ; i <= a.length ; i++)
            if(!mark.contains(i))
                result.add(i);

        return result;
    }
}

3 4

Complexity Analysis of Find All Numbers Disappeared in an Array Leetcode Solution

Time Complexity

O(N) as we traverse the whole array once to mark integers. N = size of the array.

Space Complexity

O(N) as we store all the numbers that are present in the array in a hash table. Note that we do not consider the output array in space complexity contribution.

Approach(In-place modification)

One point to notice in this problem is: “the array always contains elements less than or equal to its size”. This means there are as many indices as many distinct elements. Also, the elements missing will always be less than N(size of the array). Using this constraint, we can use the array itself to store the presence of an integer in some way. For example, assume that we could write true/false at an element’s index to denote its presence/absence respectively. In our case, the array already contains elements, so this kind of storing/memoization doesn’t seem feasible. However, since we know that all elements are positive, we can use “negative” as a sign of denoting whether we have seen an element in the array or not. Note that we can fetch the actual value stored at some index by using absolute() function which returns the absolute value of an integer. In this way, the array can be used both as a hash map and a container.

For example, if we have seen an element ‘2’ in the array, we can assign Array[1] = -1 * Array[1] which will tell us that element 2 is seen in the array.

This trick will manipulate the array in-place to store if we have seen an element at index i. Once done, we can run a loop in the range [1, N] to find all the integers that are non-negative(meaning that they have not been seen) and hence, print the required result. Note that this is only possible if we are allowed to change the array.