Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Check if Array is Consecutive Integers

Objec­tive: Given a array of unsorted num­bers, check if all the num­bers in the array are con­sec­u­tive numbers.

Exam­ples:

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: Sort­ing . Time Com­plex­ity — O(nlogn).

Bet­ter Approach: Time Com­plex­ity — O(n).

  1. Find the Max­i­mum and min­i­mum ele­ments in array (Say the array is arrA)
  2. Check if array length   = max-min+1
  3. Sub­tract the min from every ele­ment of the array.
  4. Check if array doesn’t have duplicates

for Step 4

a) If array con­tains neg­a­tive elements

  1. Cre­ate an aux array and put 0 at every position
  2. Nav­i­gate the main array and update the aux array as aux[arrA[i]]=1
  3. Dur­ing step 2 if u find any index posi­tion already filled with 1, we have dupli­cates, return false
  4. This oper­a­tion per­forms in O(n) time and O(n) space

b) If array does not con­tains neg­a­tive ele­ments — Time Com­plex­ity : O(n), Space Com­plex­ity : O(1)

  1. Nav­i­gate the array.
  2. Update the array as for ith index :- arrA[arrA[i]] = arrA[arrA[i]]*-1 (if it already not negative).
  3. If is already neg­a­tive, we have dupli­cates, return false.

Com­plete Code:


Out­put:

true
true
false

You may also like...

  • kaushal pra­jap­ati

    We can also sort the array and thn check for con­sec­u­tive num­bers by adding one to pre­vi­ous ele­ment — com­plex­ity O(nlogn)