Maximum Number of consecutive integers in an array

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; i<n; i++)
  {
    if(arr[i] == k)
      return true;
  }
  return false;
}

This 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_set<int> hash;
  for (int i = 0; i < n; i++)
    hash.insert(arr[i]);
  int max = 1; // MAX CONSECUTIVE INTEGERS
  for(int i=0; i<n; i++)
  {
    //IF PREVIOUS ELEMENT IS IN HASH,
    // THEN THIS CANNOT BE START POINT
    if(hash.find(arr[i] - 1) != hash.end())
      continue;
    int val = arr[i];
    // SEARCH NEXT INTEGER IN THE ARRAY
    while(hash.find(val+1) != hash.end())
      val++;
    if(max < (val+1 - arr[i]) )
      max = val+1 - arr[i];
  }
  return max;
}

Inserting and searching in a hash takes O(1) time, the above code takes O(n) time and O(n) extra space.