Find missing elements of a range

Difficulty Level Easy
Frequently asked in Delhivery GreyOrange LinkedIn Nagarro Opera Synopsys
Hash Larsen & Toubro SortingViews 2454

The problem Find missing elements of a range” states that you are given an array of distinct elements within a particular range and a range given as low and high. Find all the missing elements within a range which is not present in an array. The output should be in sorted order.

Example

Find missing elements of a range

arr[] = [1, 3, 5, 7, 8, 9]

low=1 high = 10
2, 4, 6, 10

Explanation

These are the missing numbers in the array within the range given as low and high i.e., 1 and 10.

arr[] = [2, 3, 7, 8]

low=1 high = 9
1, 4, 5, 6, 9

Explanation

These are the missing numbers in the array within the range given as low and high i.e., 1 and 10.

Algorithm

  1. Declare a set.
  2. Traverse the array and put all the elements into the set.
  3. While “i” is equal to low and “i” is less than equal to high.
    • If a set does not contain “i”.
      • Print ‘i’.

Explanation

We are given a problem statement that asks to find out all the missing elements in an array within a given range as low and high. To solve this we will use a set and going to store the values into the set of the given array. We are given a range as low and a high, we have to print all the elements within a low and a high inclusively.

To get that order we already store the array elements into the set. We need to run a loop initializing ‘i’ as low. we run the loop until the value of ‘i’ becomes high. Then check if the set does not contain the value ‘i’ then print ‘i’. Hence we will get all the elements that are missing from an array within a given range. Let us consider an example.

arr []={2, 3, 7, 8} low=1, high = 9

We need to traverse the array and put all the elements of an array into the set. Our set will become

set=[2,3,7,8]

In a loop initialize i to low and loop runs until high, it means ‘i’ is equal to low = 1 and high =9

i=1, if the set does not contain i, prints 1

[ 1]

i=2, set has a value ‘2’ and does nothing.

i=3, set has a value ‘3’ and does nothing.

i=4, if the set does not contain i, prints 4

[1, 4]

i=5, if the set does not contain i, prints 5

[1, 4, 5]

i=6, if the set does not contain i, prints 6

[1, 4, 5, 6]

i=7, set has a value ‘7’ and does nothing.

i=8, set has a value ‘8’ and does nothing.

i=9, if the set does not contain i, prints 1

[1, 4, 5, 6, 9]

Our output will become: [1, 4, 5, 6, 9]

Code

C++ code to Find missing elements of a range

#include <unordered_set>
#include<iostream>

using namespace std;

void getMissingElements(int arr[], int n, int low, int high)
{
    unordered_set<int> myset;
    for (int i = 0; i < n; i++)
        myset.insert(arr[i]);

    for (int x = low; x <= high; x++)
        if (myset.find(x) == myset.end())
            cout << x << " ";
}
int main()
{
    int arr[] = { 2,3,7,8 };
    int low = 1, high = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    getMissingElements(arr, n, low, high);
    return 0;
}

1 4 5 6 9

Java code to Find missing elements of a range

import java.util.HashSet;

class RangeMissingElements
{
    public static void getMissingElements(int arr[], int low, int high)
    {
        HashSet<Integer> myset = new HashSet<>();

        for (int i = 0; i < arr.length; i++)
        {
            myset.add(arr[i]);
        }

        for (int i = low; i <= high; i++)
        {
            if (!myset.contains(i))
            {
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,7,8};
        int low = 1, high = 9;
        getMissingElements(arr, low, high);
    }
}

1 4 5 6 9

Complexity Analysis

Time Complexity

O(n + (high-low+1)) where “n” is the number of elements present in the array, “high” and “low” is the input provided.

Space Complexity

O(n), in the worst case, if all elements are distinct. We’ll have to store all the elements. Thus making the algorithm require linear time.

Translate »