Missing elements in unsorted array in C++

Question

Anyone can explain to me this logic of unordered set in STL C++ because I am new to this concept.

How that they are printing missing elements of an array using an unordered set.

Is this approach is efficient or there is any other approach efficient than this one.

Logic is below:

for (int x = low; x <= high; x++)
      if (s.find(x) == s.end())
          cout << x << " ";

Full Code:

#include<iostream>
#include<vector>
#include<algorithm>
#include <unordered_set>
using namespace std;

void printMissing(int arr[], int n, int low,int high)
{

    unordered_set<int> s;
    for (int i = 0; i < n; i++)
        s.insert(arr[i]);
 
    // Traverse throught the range an print all
    // missing elements
    for (int x = low; x <= high; x++)
        if (s.find(x) == s.end())
            cout << x << " ";
}
 

int main()
{
    int arr[] = { 1, 3, 5, 4, 2, 8, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int low = 1, high = 10;
    printMissing(arr, n, low, high);
    return 0;
}

Answer 1

In the general case this will likely be the most efficient way to do it.

An unordered_set has a constant time complexity on average for insert and find so you're able to store elements you've seen before quickly in the first for loop, then go through the whole range and quickly check if you've seen them.

As an example of what constant time complexity means, let's show an example of this which does not have constant time complexity:

    // Traverse throught the range an print all
    // missing elements
    for (int x = low; x <= high; x++) {
        bool found = false;

        for (int i = 0; i < n; ++i) {
            // if one of the elements in the array matches this x we can
            // break out since the element does exist in arr
            if (arr[i] == x) {
                found = true;
                break;
            }
        }

        // was the element found? If not print it out
        if (!found) cout << x << " ";

    }

For each element in the low, high range we have to iterate over the full array if the element isn't there (which can be very very slow for large input arrays). The amount of time it takes to run this algorithm for a single element in the low, high range scales linearly with the number of elements in the array so we'd call this linear lookup time.

The constant lookup time will generally beat out the linear lookup time when the array is relatively large.