Maximum Consecutive Numbers present in an Array

Approach

The idea is to store each element in a HashSet. The set provides a unique feature of removing a similar element. The common element will therefore be handled automatically, so we don't need to worry about it. We will insert all the numbers of the array into the set. Below is the algorithm to find the count of consecutive numbers.

Algorithm

1. Declare a set, start traversing the array and insert all the numbers of the array into the set.
    
2. Again traverse the array for i=0 to i<size of the array.
    
3. Check that set contains the array[i]. If this is the case, select the current array element and store it in the temp variable.
    
4. Increase the temp values repeatedly while the set contains the temp.
    
5. The maximum between ans and temp-array[i] should be determined and stored in the ans.

Implementation in C++

#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;

int maxConsecutive(int a[], int n)
{
    // declare a set
    unordered_set<int> s;
    
    for (int i = 0; i < n; i++)
        s.insert(a[i]);
        
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (s.find(a[i] - 1) == s.end())
        {
            // store values in a temp var
            int temp = a[i];

            // check if set contains array[i]
            while (s.find(temp) != s.end())
                temp++;

            ans = max(ans, temp - a[i]);
        }
    }
    return ans;
}
int main()
{
    int array[] = {1,3,6,9,2,7};
    int size = sizeof(array) / sizeof(int);
    cout << "Maximum Consecutive number is : "<<maxConsecutive(array, size);
    cout<<endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Time Complexity

The time complexity of the above approach is O(N) because we have used unordered_set, which allows operations in constant time.

Space Complexity

The space complexity of the approach is O(N), as we are storing n elements in the unordered_set.

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

What is HashMap data structure?

A HashMap is a data structure that can map certain keys to a specific value. The values and keys could be anything.
 

Is Subarray contiguous?

Yes, A subarray is a part of an array that is contiguous. For example, if the array is {3, 1, 6} then {1, 6} can be one of the many subarrays of the original array.
 

What is HashSet in C++?

In C++, HashSet is known as unordered_set. The implementation of hash sets in the C++ standard library is known as an unordered_set. The keys' order can change depending on when they are entered into the set, and unordered_set gives no guarantees about that.

Also Read - Strong number in c

Conclusion

In this article, we have extensively discussed the problem of finding the count of maximum consecutive numbers present in an array. We solved the problem using the HashSet and discussed its time as well as space complexity.

We hope that this blog has helped you enhance your knowledge about the maximum consecutive numbers present in an array and if you like to learn more, check out our articles Implementation of HashMap, Sorting Based Problems, STL in C++, and many more on our Website.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!