Given a list of positive integers, find count of longest consecutive numbers.
Example:
Let A = {4, 5, 6, 8, 44, 69, 68, 66, 67, 7}
Ans = 5
Explanation: {4,5,6,7,8} is the longest consecutive numbers and count = 5. We do have another consecutive numbers here {66,67,68,69} but the count is 4 which is less.
Another example:
{1,2,4,3,99,100,5} output 5. since {1,2,3,4,5} is the longest consecutive numbers and count = 5.
Solution:
Step 1:
We need to iterate through the array and throw that to hashtable having the elements of the array as a key
Step 2:
We need to track if we visited each item in the list by creating an empty array same size as the given array and initialize it to false by default.
Step 3:
We need to iterate the list again only if it is not visited and check if A[i]-1 is in the hashtable. If it is present then we need to iterate till the hastable doesn't contain A[i] + 1 using a while loop.
While doing so we need to set the INDEX of Visited array we created at step 2 to be true for the array element we are visiting in the while loop. We also need to count how many elements we found to satisfy this condition.
There is a huge performance advantage by marking the numbers we visited to be true otherwise we may end up in O(N Squared) time complexity if we keep checking what we already visited in the previous checking.
The reason we need to skip what we have already visited is because once we checked a number is part of a series of consecutive number and count the length of this temp series, we are sure that it wont appear in another series we will start to count as far as this serious is concerned.
example:
1,2,4,3, 8,10,9,11,12
There are two series in this example. The first one {1,2,3,4} and second is {8,9,10,11,12}
Here once we visited all the elements of the first array, we don't have to go through over them when we do the same process for the second series. That is the benefit of tracking the Visited status.
Step 4:
We need to have max count variables which is the largest of count and max count.
public static int LongestConsecutive(int[] A) {
if (A.Length == 0)
return 0;
int n = A.Length;
int count = 0;
int maxcount = 0;
Hashtable hs = new Hashtable();
bool[] visited = new bool[A.Length];
for (int i = 0; i < n; i++) {
if (!hs.ContainsKey(A[i]))
hs.Add(A[i], i);
visited[i] = false;
}
for (int i = 0; i < n; i++) {
count = 0;
if (!visited[i]) {
int num = A[i];
if (!hs.Contains(num - 1)) {
while (hs.Contains(num + 1)) {
num++; count++;
visited[(int)hs[num]] = true;
}
maxcount = Math.Max(count, maxcount);
}
}
}
return maxcount + 1;
}
For type safety and performance we can use dictionaries instead of hashatable and avoid the boxing and unboxing.