Check if Array Contains Contiguous Integers With Duplicates Allowed

You are given an array of integers which can contain duplicate elements as well. The problem statement asks to find out if it is a set of contiguous integers, print “Yes” if it is, print “No” if it is not.

Example

Sample Input:

[2, 3, 4, 1, 7, 9]

Sample Output:

Yes

Explanation:

It has a set of contiguous integers of the number [2, 3, 4, 1]

Algorithm to check if the array contains contiguous integers with duplicates allowed

1. Declare a Set.
2. Add all the elements of an array into the Set.
3. Set count to 1 and currentElement to arr[0]-1.
4. Open a loop, while Set contains the currentElement.
  1. Do count++ and currentElement--.
5. Set currentElement to arr[0]+1.
6. Open a loop, while Set contains the currentElement.
  1. Do count++ and currentElement++.
7. Check if the count is equal to the size of a set, if condition satisfies, then return true.
8. Else return false.

Explanation

We are given a question to determine if the given array has a set of contiguous integers. If it has then print Yes else print No. We are going to use a set as it is going to remove all the duplicate elements and make our work easy. Set provides a future if it has many elements in which some are duplicate elements. Then it is going to remove all the duplicates and contain only distinct elements.

We are going to insert all the elements by traversing the array into Set and it will have distinct elements now. Set the value of count to 1 and we will keep on increasing it in later operations. It will check the size of the contiguous set of the integers because it will have a different size than Set if there are no contiguous integers present in an array. The arr[0] -1 would be the value of currentElement. It will keep an eye on the set of integers.

Open a loop and it will keep going till Set has the currentElement in it, because in a loop we are going to increase the value of count by 1(count=count + 1) and decrease the value of currentElement by 1 (currentElement = currentElement – 1). Set the value of currentElement to arr[0]+1 and open another loop and it will also keep going till Set has the currentElement in it, but this time we will increase both the values by 1 count++ and currentElement++. At last, we will check if the value of count is equal to the size of Set, if it is found to be true then return true else return false.

Let us consider an example:

Example

arr[]={ 5, 2, 3, 6, 4, 4, 6, 6 };

After traversing the array, we will have the following values in Set.

Set:{2,3,4,5,6}, as it removes duplicate elements

Count =1, currentElement = arr[0]-1=4;

• While Set has currentElement(4) is true,

Count=count+1=> count =2, currentElement– => currentElement=3

• While Set has currentElement(3) is true,

Count=count+1=> count =3, currentElement– => currentElement=2

• While Set has currentElement(2) is true,

Count=count+1=> count =4, currentElement– => currentElement=1

• While Set has currentElement(1) is false, so it comes out of the loop.

Set currentElement[0]=arr[0]+1 => currentElement=6

• While Set has currentElement(6) is true,

Count=count+1=> count =5, currentElement++ => currentElement=7

• While Set has currentElement(7) is false so it comes out of the loop

And it will check if the count is equal to the size of the set and the condition satisfy so it will return true and in the main function yes will be printed.

Implementation

C++ code to check if the array contains contiguous integers with duplicates allowed

#include<iostream>
#include<unordered_set>
using namespace std;
bool areElementsContiguous(int arr[], int n)
{
    unordered_set<int> Set;
    for (int i = 0; i < n; i++)
        Set.insert(arr[i]);

    int count = 1;
    int currentElement = arr[0] - 1;
    while (Set.find(currentElement) != Set.end())
    {
        count++;
        currentElement--;
    }
    currentElement = arr[0] + 1;
    while (Set.find(currentElement) != Set.end())
    {
        count++;
        currentElement++;
    }
    return (count == (int)(Set.size()));
}
int main()
{
    int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (areElementsContiguous(arr, n))
        cout << "Yes, it is set of contiguous integers.";
    else
        cout << "No, it is not a set of contiguous integers.";
    return 0;
}

Yes, it is set of contiguous integers.

Java code to check if the array contains contiguous integers with duplicates allowed

import java.util.HashSet;
class contiguousArray
{
    public static Boolean checkContiguousElements(int arr[], int n)
    {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            set.add(arr[i]);
        }
        int count = 1;
        int currentElement = arr[0] - 1;
        while (set.contains(currentElement) == true)
        {
            count++;
            currentElement--;
        }
        currentElement = arr[0] + 1;
        while (set.contains(currentElement) == true)
        {
            count++;
            currentElement++;
        }
        return (count == (set.size()));
    }
    public static void main(String[] args)
    {
        int arr[] = { 10, 7, 8, 11, 9, 9, 10, 10 };
        int n = arr.length;
        if (checkContiguousElements(arr, n))
            System.out.println("Yes, it is set of contiguous integers.");
        else
            System.out.println("No, it is not a set of contiguous integers.");
    }
}

Yes, it is set of contiguous integers.

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array.

Space Complexity

O(n) where “n” is the number of elements in the array.