Longest Consecutive Elements Sequence, by Microsoft

This problem comes via Daily Coding Problem:

This problem was asked by Microsoft.

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, given [100, 4, 200, 1, 3, 2], the longest consecutive element sequence is[1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

The idea is to use some extra space (O(n)-space) to accomplish an O(n)-time solution. Basically we'll make use of two hash tables:

• First one contains all the (unique) numbers from the input array
• Second one will be used later to mark the "visited" numbers

As you progress thru the first hash table, then do a "search" to the left and to the right looking for non-visited numbers. As you continue, increase your current sequence length. A very important point is to upon visiting any number, always mark it as visited. This will guarantee the linearity of your solution: each number will be at most seen twice: first by the outer loop, and occasionally (once) by the inner loop, for a total of 2n-time, or O(n)-time and O(n)-space.

If you run it against this sequence:

4, 1, 3, 2, 7, 8, 9, 6, 100, 2000, 6, 5, 13, 14, -1, 12, 13, 14, 15, 16, 17, 18, 19

You will see that the answer is 9 (from 1..9). Add a "0" at the end and your result changes to 11 (from -1..9). Code is checked-in on GitHub here: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem12222018.cs and also down below. Cheers, Marcelo.

class DailyCodingProblem12222018
{
 public int LongestConsecutiveElementSequence(int[] numbers)
 {
  if (numbers == null) return 0;

  //O(n)-time and O(n)-space
  Hashtable count = new Hashtable();
  for (int i = 0; i < numbers.Length; i++) if (!count.ContainsKey(numbers[i])) count.Add(numbers[i], true);

  //O(n)-time and O(n)-space
  //Each cell is only visited at most twice for a total of 2n-time and 2n-space, hence O(n) for both
  int longestSequenceLength = 0;
  Hashtable visited = new Hashtable();
  foreach(int n in count.Keys)
  {
   if (!visited.ContainsKey(n))
   {
    visited.Add(n, true);
    int current = 1;

    //Left
    int left = n - 1;
    while (!visited.ContainsKey(left) && count.ContainsKey(left))
    {
     visited.Add(left, true);
     left--;
     current++;
    }

    //Right
    int right = n + 1;
    while (!visited.ContainsKey(right) && count.ContainsKey(right))
    {
     visited.Add(right, true);
     right++;
     current++;
    }

    longestSequenceLength = Math.Max(longestSequenceLength, current);
   }
  }

  return longestSequenceLength;
 }
}