Find the length of maximum number of consecutive numbers jumbled up in an array.
Examples:
Input : arr[] = {1, 94, 93, 1000, 5, 92, 78}; Output : 3 The largest set of consecutive elements is 92, 93, 94 Input : arr[] = {1, 5, 92, 4, 78, 6, 7}; Output : 4 The largest set of consecutive elements is
4, 5, 6, 7
The idea is to use hashing. We traverse through the array and for every element, we check if it is the starting element of its sequence. If yes then by incrementing its value we search the set and increment the length. By repeating this for all elements, we can find the lengths of all consecutive sets in array. Finally we return length of the largest set.
- C++
- Java
- Python3
- C#
- Javascript
3
Time complexity : O(n2)
Space complexity: O(n)
Another approach: The idea is to sort the array. We will traverse through the array and check if the difference between the current element and the previous element is one or not. If the difference is one we will increment the count of the length of the current sequence. Otherwise, we will check if the count of the length of our current subsequence is greater than the length of our previously counted sequence. If it is, we will update our answer and then we will update the count to one to start counting the length of another sequence. By repeating this for all elements, we can find the lengths of all consecutive sequences in the array. Finally, we return the length of the largest sequence.
- C++
- Java
- Python3
- C#
3
Time complexity : O(nlogn)
Space complexity: O(1)
Another approach: The idea is to use hashing. We traverse through the array and for every element, we check if it is the starting element of its sequence( no element whose value is less than the current element by one is present in the set ). If yes then by incrementing its value we search for other valid elements that could be present in the set and increment the length of the sequence accordingly. By repeating this for all elements, we can find the lengths of all consecutive sequences in the array. Finally, we return the length of the largest sequence
- Python3
3
Time complexity: O(n)
Space complexity: O(n)