# Interview Questions

# Maximum consecutive integers present in an array

- October 14, 2018
- Posted by: Kamal Rawat
- Category: Algorithms

Given an array of integers. Find the maximum number of consecutive integers present in the array. For example, if the array is:

int arr[] = { 2, 24, 22, 60, 56, 23, 25};

Then the answer should be 4, because there are 4 consecutive integers present in the array (22, 23, 24, 25).

**Solution:**

The brute-force way is to traverse the array, and for each element find the maximum length of consecutive integers present in the array if this element (current element) is the starting point.

int maxConsecutiveLength(int*arr, int n) { int max = 1; // MAX CONSECUTIVE INTEGERS for(int i=0; i<n; i++) { int val = arr[i]; // SEARCH NEXT INTEGER IN THE ARRAY while(findInArray(arr, n, val+1)) val++; if(max < (val+1 - arr[i]) ) max = val+1 - arr[i]; } return max; }

The function findInArray, search for a value in the array using linear search.

// FIND A VALUE (k) IN THE ARRAY. LINEAR SEARCH bool findInArray(int*arr, int n, int k) { for(int i=0; iThis is the problem in the code, that we are searching in the array a lot of time.

This search can be improved if we store all the values in a hashtable.

Solution-2: Using Hashtable

Below solution is same as the previous one, except for one thing. Here we are not searching in the array linearly, instead we are using O(n) extra memory to store all the values in a hashtable and then search in that hashtable in constant time:int maxConsecutiveLength(int*arr, int n) { // INSERT ALL ELEMENTS IN A SORTED SET unordered_sethash; for (int i = 0; i < n; i++) hash.insert(arr[i]); int max = 1; // MAX CONSECUTIVE INTEGERS for(int i=0; i Inserting and searching in a hash takes O(1) time, the above code takes O(n) time and O(n) extra space.