Check if array contains contiguous integers with duplicates allowed

Example

Input

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

Output

Yes

Contiguous set of integers: {3, 4, 5, 6}

Brute Force Approach

1. Firstly, we will sort the given array.
2. Now, we will traverse the array and check that every consecutive number will differ by at most by one.

Algorithm using the hash table

1. Add each component to the hash table.
2. Select the first element now, and keep increasing its value by 1 until you discover a value that isn't listed in the hash table.
3. Pick the first element once more, then keep lowering its value by 1 until you discover one that isn't in the hash table.
4. Count all the elements in the hash table you created using this method.
5. Print "Yes" if the count equals the hash size. Otherwise, "No."

C++ Code

/* C++ program to check if array contains contiguous integers with duplicates allowed */
#include <bits/stdc++.h>

using namespace std;
 
/* function to check the required condition */
bool areElementsContiguous(int arr[], int n) {

	/* Storing elements of array in a hash table "hash" */
	unordered_set<int> hash;
	for (int i = 0; i < n; i++)
		hash.insert(arr[i]);

	/* as arr[0] is present in 'hash' */
	int count = 1;
	int element = arr[0] - 1;

	/* check "element" is present in 'hash' */
	while (hash.find(element) != hash.end()) {
		/* increment count */
		count++;

		/* decrement element */
		element--;
	}

	element = arr[0] + 1;
	
	/* check "element" is present in 'hash' */
	while (hash.find(element) != hash.end()) {
		/* increment count */
		count++;
 		
		/* increment element */
		element++;
	}
 
	/* return true if required condition satisfies else false */
	return (count == (int)(hash.size()));
}

/* Main program */
int main()
{
    /* Input array */
	int arr[] = { 5, 3, 6, 4, 4, 6 };

	/* Size of an input array */
	int n = sizeof(arr) / sizeof(arr[0]);

	/* Printing required output */
	if (areElementsContiguous(arr, n))
		cout << "Yes";
	else
		cout << "No";

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java Code

/* Java program to check if the array contains contiguous integers */
import java.io.*;
import java.util.*;
 
class Main {
    
	/* function to check the required condition */
	static Boolean areElementsContiguous(int arr[], int n) {
    	
		/* Storing elements of array in a hash table "hash" */
		HashSet<Integer> hash = new HashSet<Integer>();

		for (int i = 0; i < n; i++)
			hash.add(arr[i]);
 		
		/* as arr[0] is present in 'hash' */
		int count = 1; 		
		int element = arr[0] - 1;

		/* check "element" is present in 'hash' */
		while (hash.contains(element) == true) {
			/* increment count */
     		count++;
    		
     		/* decrement element */
     		element--;
		}
 		
		element = arr[0] + 1;

		/* check "element" is present in 'hash' */
		while (hash.contains(element) == true) {
			/* increment count */
     		count++;
    		
     		/* increment element */
     		element++;
		}
		
		/* return true if required condition satisfies else false */
		return (count == (hash.size()));
	}
 	
	/* Main program */
	public static void main(String[] args)
	{
    	/* Input array */
		int arr[] = { 5, 3, 6, 4, 4, 6 };

		/* Size of an input array */
		int n = arr.length;

		/* Printing required output */
		if (areElementsContiguous(arr, n))
			System.out.println("Yes");
		else
			System.out.println("No");
	}
}

You can also try this code with Online Java Compiler

Run Code

Input

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

Output

Yes

Complexities

Time complexity 

O(n), where n is the size of an array
Reason: This method requires traversing the array only once, so the time complexity will be O(n).

Space complexity

O(n), where n is the size of an array
Reason: Required an O(n) space to store values.

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

What do you mean by HashTable?

A hash table associates various keys with various values. Hash table implements the map, the serializable, and cloneable interfaces and inherits the dictionary type.

What are the hash table's three fundamental operations?

The fundamental principle operations of a hash table are: search which searches for an element in the hash table, Insert which adds a new element to the hash table, and Delete which removes an element from the hash table.

What is the load factor of a hash table?

Load factor can be defined as (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased and n is the overall size of the hash table.

How come hash tables are quick?

The linear time complexity of O(n) is required when searching through an array-like data structure that is the search time grows linearly in proportion to the size of the data structure. Simply, searching through an array is slower than using a hash table.

What is the time complexity of a hash table?

No matter how many entries are in the table, hash tables typically offer constant-time O(1) lookup. The majority of hash table schemes have an O(n) worst-case lookup time.

Conclusion

In this article, we have checked if the array contains contiguous integers with duplicates allowed. We hope that this blog will help you understand the concept of a hash table, and if you want to learn more about the hash table, check out our other blogs on the hashtable, hashtable vs stl map, the difference between hashmap and hashtable, and Hash Function in Data Structure.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!