Check if Array is Consecutive Integers | Algorithms

Check if Array is Consecutive Integers | Algorithms
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)

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.

   public Boolean WihtOutAuxArray(int [] arrA){

        //this method with work if numbers are non negative

        int max = findMax(arrA);

        int min = findMin(arrA);

        if(arrA.length!=max-min+1) return false;

        for(int i = 0;i<arrA.length;i++){

            arrA[i] = arrA[i]-min+1;

        }

        for(int i = 0;i<arrA.length;i++){

            int x  = Math.abs(arrA[i]);

            if(arrA[x-1]>0){

                arrA[x-1] = arrA[x-1]*-1;

            }

            else{

                return false;

            }

        }

        return true;

    }

    public Boolean withAuxArray(int [] arrA){

        // this method with work even if numbers are negative

        int []  aux = new int [arrA.length];
// why not just use hashmap?

        int max = findMax(arrA);

        int min = findMin(arrA);

        if(arrA.length!=max-min+1) return false;

        for(int i = 0;i<arrA.length;i++){

            arrA[i] = arrA[i]-min;

            aux[i] = 0;

        }

        for(int i = 0;i<arrA.length;i++){

            if(aux[arrA[i]]==0){

                aux[arrA[i]]=1;

            }

            else{

                return false;

            }

        }

        //If we have reached till here means , we satisfied all the requirements

        return true;

    }

Related:
http://algorithms.tutorialhorizon.com/find-the-element-which-appears-maximum-number-of-times-in-the-array/

Objec­tive: Given an array of inte­gers, write a algo­rithm to find the ele­ment which appears max­i­mum num­ber of times in the array.

Bet­ter Solu­tion : Use Hashmap. Store the count of each ele­ment of array in a hash table and later check in Hash map which ele­ment has the max­i­mum count 

public void maxRepeatingElementUsingSorting(int [] arrA){
    if(arrA.length<1){
        System.out.println("Inavlid Array");
        return;
    }
    Arrays.sort(arrA);
    int count=1;
    int maxCount=1;
    int currentElement = arrA[0];
    int maxCountElement =arrA[0];
    for (int i = 1; i <arrA.length ; i++) {
        if(currentElement==arrA[i]){
            count++;
        }else{
            if(count>maxCount){
                maxCount = count;
                maxCountElement = currentElement;
            }
            currentElement = arrA[i];
            count = 1;
        }
    }
    System.out.println("Element repeating maximum no of times: " + maxCountElement + ", maximum count: " + maxCount);
}

Bet­ter Solu­tion (Con­di­tional) : O(n) time and O(1) extra space.

• This solu­tion works only if array has pos­i­tive inte­gers and all the ele­ments in the array are in range from 0 to n-1 where n is the size of the array.
• Nav­i­gate the array.
• Update the array as for ith index :- arrA[arrA[i]% n] = arrA[arrA[i]% n] + n;
• Now nav­i­gate the updated array and check which index has the max­i­mum value, that index num­ber is the ele­ment which has the max­i­mum occur­rence in the array.

public void MaxRepeatingElementInPlace(int [] arrA){
    int size = arrA.length;
    int maxCount=0;
    int maxIndex=0;
    for (int i = 0; i <size ; i++) {
        //get the index to be updated
        int index = arrA[i]% size;
        arrA[index] = arrA[index] + size;
    }
    for (int i = 0; i <size ; i++) {
        if(arrA[i]/size>maxCount){
            maxCount=arrA[i]/size;
            maxIndex=i;
        }
    }
    System.out.println("Element repeating maximum no of times: " + arrA[maxIndex]%size + ", maximum count: " + maxCount);
}

http://algorithms.tutorialhorizon.com/find-duplicates-in-an-given-array-in-on-time-and-o1-extra-space/

Given an array of inte­gers, find out dupli­cates in it.

Bet­ter Solu­tion : Use Hash map. Store the count of each ele­ment of array in a hash table and later check in Hash table if any ele­ment has count more than 1

Bet­ter Solu­tion (Con­di­tional) : O(n) time and O(1) extra space.

• This solu­tion works only if array has pos­i­tive inte­gers and all the ele­ments in the array are in range from 0 to n-1 where n is the size of the array.
• Nav­i­gate the array.
• Update the array as for ith index :- arrA[arrA[i]] = arrA[arrA[i]]*-1 (if it already not negative).
• If is already neg­a­tive, we have dupli­cates, return false.

Note:

• The code given below does not han­dle the case when 0 is present in the array.
• To han­dle 0 in array, while nav­i­gat­ing the array, when 0 is encoun­tered, replace it with INT_MIN and if INT_MIN is encoun­tered while tra­vers­ing, this means 0 is repeated in the array.

public void hasDuplicates(int[] arrA) {

    for (int i = 0; i < arrA.length; i++) {
        //check if element is negative, if yes the we have found the duplicate
        if (arrA[Math.abs(arrA[i])] < 0) {
            System.out.println("Array has duplicates : " + Math.abs(arrA[i]));
        } else {
            arrA[Math.abs(arrA[i])] = arrA[Math.abs(arrA[i])] * -1;
        }
    }
}

Read full article from Check if Array is Consecutive Integers | Algorithms