Find All Numbers Disappeared in an Array Leetcode Solution


Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Google Microsoft Yahoo
Array Hashing

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}
n

Find All Numbers Disappeared in an Array Leetcode Solution

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

  1. Initialize a hash set mark[Integer] to store elements that are present.
  2. For every element i in the array:
    • Add i to mark
  3. Initialize a List/vector result to store missing elements in the array
  4. For every element in the range: [1, N]:
    • If is not present in mark:
      • Add it to result
  5. Return result
  6. 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.

Algorithm

  1. For every element in the array:
    • If Array[i – 1] > 0:
      • Set this as negative, or, Array[i – 1] *= -1;
  2. Initialize a List/vector result to store all the missing elements
  3. For every integer in the range [1, N](N =size of the array):
    • If Array[i] > 0
      • Add this element i to result
  4. Return result
  5. 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)
{
    int N = a.size();
    int idx;
    for(int i = 0 ; i < N ; i++)
    {
        idx = abs(a[i]) - 1;
        if(a[idx] > 0)
            a[idx] *= -1;
    }

    vector <int> result;
    for(int i = 0 ; i < N ; i++)
        if(a[i] > 0)
            result.emplace_back(i + 1);

    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.*;
import java.lang.Math;

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)
    {
        int idx;
        for(int i = 0 ; i < a.length ; i++)
        {
            idx = Math.abs(a[i]) - 1;
            if(a[idx] > 0)
                a[idx] *= -1;
        }

        List <Integer> result = new ArrayList <Integer> ();

        for(int i = 0 ; i < a.length ; i++)
            if(a[i] > 0)
                result.add(i + 1);

        return result;
    }
}
3 4

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

Time Complexity

O(N) as we run two passes of the array irrespective of the input to find the missing elements. N = size of the array.

Space Complexity 

O(1) as we use constant memory space.