Sorting: Find the missing element of a range in an array

Problem Statement:

You are given a array of a range.

There are some numbers missing.

You need to find how many numbers needs to be added to make the range complete

Example:

Input [3, 4, 7, 6]

Output: 1

You need to add 5 to make the range complete from [3, 4, 5, 6, 7]

Solution 1: Sorting

Sort the array.

Check if the elements are consecutive or not.

If not, then increment the count

Time Complexity: O(n log n)
Space Complexity: O(1)

Solution 2: Hashing

Push the elements into the hash.

Store the minimum and maximum element.

Traverse the hash map, and count the element not in hash

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>

using namespace std;


int solution_1(vector<int>& arr)
{
    int count = 0;

    sort(arr.begin(), arr.end());

    for (int i = 0; i < arr.size() - 1; i++)
        if (arr[i] != arr[i + 1] && arr[i] != arr[i + 1] - 1)
            count += arr[i + 1] - arr[i] - 1;

    return count;
}

int solution_2(vector<int> arr)
{
    unordered_set<int> s;
    int count = 0;
    int max_m = INT_MIN;
    int min_m = INT_MAX;

    for (int i = 0; i < arr.size(); i++) {
        s.insert(arr[i]);
        if (arr[i] < min_m)
            min_m = arr[i];
        if (arr[i] > max_m)
            max_m = arr[i];
    }

    // The missing element count
    return (max_m - min_m + 1) - s.size();
}



int main()
{
    vector<int> arr = { 3, 4, 7, 6 };
    cout << solution_1(arr) << endl;
    cout << solution_2(arr) << endl;
    return 0;
}

Output

1
1