Objective: Given a array of unsorted numbers, check if all the numbers in the array are consecutive numbers.

Examples:

int [] arrA = {21,24,22,26,23,25}; - True
(All the integers are consecutive from 21 to 26)
int [] arrB = {11,10,12,14,13}; - True
(All the integers are consecutive from 10 to 14)
int [] arrC = {11,10,14,13}; - False
(Integers are not consecutive, 12 is missing)

Approach:

Naive Approach: Sorting . Time Complexity – O(nlogn).

Better Approach: Time Complexity – O(n).

Find the Maximum and minimum elements in array (Say the array is arrA)

Check if array length = max-min+1

Subtract the min from every element of the array.

Check if array doesn’t have duplicates

for Step 4

a) If array contains negative elements

Create an aux array and put 0 at every position

Navigate the main array and update the aux array as aux[arrA[i]]=1

During step 2 if u find any index position already filled with 1, we have duplicates, return false

This operation performs in O(n) time and O(n) space

b) If array does not contains negative elements – Time Complexity : O(n), Space Complexity : O(1)

Navigate the array.

Update the array as for ith index :- arrA[arrA[i]] = arrA[arrA[i]]*-1 (if it already not negative).

If is already negative, we have duplicates, return false.

Complete Code:

Output:

true
true
false

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________