Maximum Consecutive Numbers Present in an Array

Problem Statement

Suppose you have an array of integers of size N. The problem “Maximum consecutive numbers present in an array” asks to find out the maximum count of consecutive numbers that could be scattered in an array.

Example

arr[] = {2, 24, 30, 26, 99, 25}

3

Explanation: The consecutive numbers are ⇒ 24, 25, 26 (A set of 3).

arr[] = { -8, 9 , -1, -6, -5}

2

Explanation: The consecutive numbers are ⇒ -6, -5 (A set of 2).

Algorithm

1. Declare a set.
2. Do traversing of the array, and insert all the values of array into the Set.
3. Set output to 0.
4. Traverse the array from i=0, to i<n(length of the array).
  1. Check if Set contains the arr[i].
    1. If true, then pick the current array element and store it to temp.
  2. While Set contains the temp, repeatedly increases the values of temp.
  3. Find out the maximum between output and temp-arr[i] and store it into the output.
5. Return output.

Explanation

Given an integer array, we have to find out the highest count of consecutive numbers present in an array. We are going to use a set. Set provides a feature of removing a similar element. So, we need not worry about the handle the common element, it will be handled automatically.

We are going to add all the values of array into the Set. Because later on, we are going to check consecutive numbers as well. We will traverse the array again, picking each element and check if the map has that arr[i], if true then we are going to pick that element into a temporary variable and check that again if a map contains that temp, if true, then increase the value of temp by 1, and then check again, and again increase it, continues this till the map doesn’t have that incremented value. Now, when we come out of this loop, we will the most incremented value of current array element which is present in a map, also we increasing it by the count of 1, so it will also be consecutive numbers as well.

We now have to find out the maximum of output and the difference of temp-arr[i], do not think as if this difference gives the wrong number of the count, as we will get the incremented value of temp while coming out of the loop, we will get the correct count of consecutive numbers present. We will then store the maximum between output and the difference of temp-arr[i] (output, temp-arr[i]). Arr[i] is just a starting point for a series of consecutive numbers and temp, ending point. These steps will be repeated until we found the maximum output after while traversing the whole array.

Implementation

C++  program to find Maximum Consecutive Numbers Present in an Array

#include<iostream>
#include<unordered_set>

using namespace std;

int getMaxConsecutiveNumber(int arr[], int n)
{
    unordered_set<int> SET;
    for (int i = 0; i < n; i++)
        SET.insert(arr[i]);

    int output = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr[i] - 1) == SET.end())
        {
            int temp = arr[i];

            while (SET.find(temp) != SET.end())
                temp++;

            output = max(output, temp - arr[i]);
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 24, 30, 26, 99, 25 };
    int n = sizeof(arr) / sizeof(int);
    cout << "Largest Set found : "<<getMaxConsecutiveNumber(arr, n)<< endl;
    return 0;
}

Largest Set found : 3

Java program to find Maximum Consecutive Numbers Present in an Array

import java.util.HashSet;

class LargestConsecutiveSet
{
    public static int getMaxConsecutiveNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
        }
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if(SET.contains(arr[i]))
            {
                int temp = arr[i];
                while (SET.contains(temp))
                    temp ++;

                output = Math.max(output, temp - arr[i]);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2, 24, 30, 26, 99, 25};
        int n = arr.length;
        System.out.println("Largest Set found : "+getMaxConsecutiveNumber(arr, n));
    }
}

Largest Set found : 3

Complexity Analysis for find Maximum Consecutive Numbers Present in an Array

Time Complexity

O(n) where “n” is the number of elements in the array. Because we have used HashSet, which allows the insertion, deletion, and searching operation in constant time.

Space Complexity

O(n) where “n” is the number of elements in the array. We have stored N elements in the set thus linear space complexity.

Reference