Longest Consecutive Sequence in an Unsorted Array [duplicate]

Question

You are given an Array of numbers and they are unsorted/random order. You are supposed to find the longest sequence of consecutive numbers in the array. Note the sequence need not be in sorted order within the array. Here is an example :

Input :

A[] = {10,21,45,22,7,2,67,19,13,45,12,11,18,16,17,100,201,20,101}  

Output is :

{16,17,18,19,20,21,22}  

The solution needs to be of O(n) complexity.

I am told that the solution involves using a hash table and I did come across few implementations that used 2 hash tables. One cannot sort and solve this because sorting would take O(nlgn) which is not what is desired.

Answer 1

You could have two tables:

• Start table: (start-point, length)
• End table: (ending-point, length)

When adding a new item, you would check:

• Does value + 1 exist in start table? If so, delete it and create a new entry of (value, length + 1) where length is the "current" length. You'd also update the end table with the same end point but greater length.
• Does value - 1 exist in the end table? If so, delete it and create a new entry of (value, length + 1), and this time update the start table (the starting position will be the same, but the length will be increased)

If both conditions hold, then you're effectively stitching two existing sequences together - replace the four existing entries with two new entries, representing the single longer sequence.

If neither condition holds, you just create a new entry of length 1 in both tables.

After all the values have been added, you can just iterate over the start table to find the key with the largest value.

I think this would work, and would be O(n) if we assume O(1) hash lookup/add/delete.

EDIT: C# implementation. It took a little while to get right, but I think it works :)

using System;
using System.Collections.Generic;

class Test
{
    static void Main(string[] args)
    {
        int[] input = {10,21,45,22,7,2,67,19,13,45,12,
                11,18,16,17,100,201,20,101};

        Dictionary<int, int> starts = new Dictionary<int, int>();
        Dictionary<int, int> ends = new Dictionary<int, int>();

        foreach (var value in input)
        {
            int startLength;
            int endLength;
            bool extendsStart = starts.TryGetValue(value + 1,
                                                   out startLength);
            bool extendsEnd = ends.TryGetValue(value - 1,
                                               out endLength);

            // Stitch together two sequences
            if (extendsStart && extendsEnd)
            {
                ends.Remove(value + 1);
                starts.Remove(value - 1);
                int start = value - endLength;
                int newLength = startLength + endLength + 1;
                starts[start] = newLength;
                ends[start + newLength - 1] = newLength;
            }
            // Value just comes before an existing sequence
            else if (extendsStart)
            {
                int newLength = startLength + 1;
                starts[value] = newLength;
                ends[value + newLength - 1] = newLength;
                starts.Remove(value + 1);
            }
            else if (extendsEnd)
            {
                int newLength = endLength + 1;
                starts[value - newLength + 1] = newLength;
                ends[value] = newLength;
                ends.Remove(value - 1);
            }
            else
            {
                starts[value] = 1;
                ends[value] = 1;
            }
        }

        // Just for diagnostics - could actually pick the longest
        // in O(n)
        foreach (var sequence in starts)
        {
            Console.WriteLine("Start: {0}; Length: {1}",
                              sequence.Key, sequence.Value);
        }
    }
}

---

EDIT: Here's the single-hashset answer implemented in C# too - I agree, it's simpler than the above, but I'm leaving my original answer for posterity:

using System;
using System.Collections.Generic;
using System.Linq;

class Test
{
    static void Main(string[] args)
    {
        int[] input = {10,21,45,22,7,2,67,19,13,45,12,
                11,18,16,17,100,201,20,101};

        HashSet<int> values = new HashSet<int>(input);

        int bestLength = 0;
        int bestStart = 0;
        // Can't use foreach as we're modifying it in-place
        while (values.Count > 0)
        {
            int value = values.First();
            values.Remove(value);
            int start = value;
            while (values.Remove(start - 1))
            {
                start--;
            }
            int end = value;
            while (values.Remove(end + 1))
            {
                end++;
            }

            int length = end - start + 1;
            if (length > bestLength)
            {
                bestLength = length;
                bestStart = start;
            }
        }
        Console.WriteLine("Best sequence starts at {0}; length {1}",
                          bestStart, bestLength);
    }
}

Answer 2

Dump everything to a hash set.

Now go through the hashset. For each element, look up the set for all values neighboring the current value. Keep track of the largest sequence you can find, while removing the elements found from the set. Save the count for comparison.

Repeat this until the hashset is empty.

Assuming lookup, insertion and deletion are O(1) time, this algorithm would be O(N) time.

Pseudo code:

 int start, end, max
 int temp_start, temp_end, count

 hashset numbers

 for element in array:
     numbers.add(element)

 while !numbers.empty():
     number = numbers[0]
     count = 1
     temp_start, temp_end = number 

     while numbers.contains(number - 1):
         temp_start = number - 1; count++
         numbers.remove(number - 1)

     while numbers.contains(number + 1):
         temp_end = number + 1; count++
         numbers.remove(number + 1)

     if max < count:
         max = count
         start = temp_start; end = temp_end

 max_range = range(start, end)

The nested whiles don't look pretty, but each number should be used only once so should be O(N).

Answer 3

Here is a solution in Python that uses just a single hash set and doesn't do any fancy interval merging.

def destruct_directed_run(num_set, start, direction):
  while start in num_set:
    num_set.remove(start)
    start += direction
  return start

def destruct_single_run(num_set):
  arbitrary_member = iter(num_set).next()
  bottom = destruct_directed_run(num_set, arbitrary_member, -1) 
  top = destruct_directed_run(num_set, arbitrary_member + 1, 1)
  return range(bottom + 1, top)

def max_run(data_set):
  nums = set(data_set)
  best_run = []
  while nums:
    cur_run = destruct_single_run(nums)
    if len(cur_run) > len(best_run):
      best_run = cur_run
  return best_run

def test_max_run(data_set, expected):
  actual = max_run(data_set)
  print data_set, actual, expected, 'Pass' if expected == actual else 'Fail'

print test_max_run([10,21,45,22,7,2,67,19,13,45,12,11,18,16,17,100,201,20,101], range(16, 23))
print test_max_run([1,2,3], range(1, 4))
print max_run([1,3,5]), 'any singleton output fine'

Answer 4

Another solution is with hash search which runs in O(n)

int maxCount = 0;
for (i = 0; i<N; i++) 
{ 
    // Search whether a[i] - 1 is present in the list.If it is present, 
    // you don't need to initiate count since it  will be counted when 
    // (a[i] - 1) is traversed.
    if (hash_search(a[i]-1))
        continue;

    // Now keep checking if a[i]++ is present in the list, increment the count
    num = a[i]; 
    while (hash_search(++num)) 
        count++;

    // Now check if this count is greater than the max_count got previously 
    // and update if it is
    if (count > maxCount)
    {
        maxIndex = i;
        count = maxCount;
    }
}

Answer 5

Here is the implementation:

static int[] F(int[] A)
{
    Dictionary<int, int> low = new Dictionary<int, int>();
    Dictionary<int, int> high = new Dictionary<int, int>();

    foreach (int a in A)
    {
        int lowLength, highLength;

        bool lowIn = low.TryGetValue(a + 1, out lowLength);
        bool highIn = high.TryGetValue(a - 1, out highLength);

        if (lowIn)
        {
            if (highIn)
            {
                low.Remove(a + 1);
                high.Remove(a - 1);
                low[a - highLength] = high[a + lowLength] = lowLength + highLength + 1;
            }
            else
            {
                low.Remove(a + 1);
                low[a] = high[a + lowLength] = lowLength + 1;
            }
        }
        else
        {
            if (highIn)
            {
                high.Remove(a - 1);
                high[a] = low[a - highLength] = highLength + 1;
            }
            else
            {
                high[a] = low[a] = 1;
            }
        }
    }

    int maxLow = 0, maxLength = 0;
    foreach (var pair in low)
    {
        if (pair.Value > maxLength)
        {
            maxLength = pair.Value;
            maxLow = pair.Key;
        }
    }

    int[] ret = new int[maxLength];
    for (int i = 0; i < maxLength; i++)
    {
        ret[i] = maxLow + i;
    }

    return ret;
}

Answer 6

class Solution {
public:
    struct Node{
        int lower;
        int higher;
        Node(int l, int h):lower(l),higher(h){

    }
};
int longestConsecutive(vector<int> &num) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    map<int,Node> interval_map;
    map<int,Node>::iterator curr_iter,inc_iter,des_iter;

    //first collect
    int curr = 0;
    int max = -1;
    for(size_t i = 0; i < num.size(); i++){
        curr = num[i];
        curr_iter = interval_map.find(curr);
        if (curr_iter == interval_map.end()){
            interval_map.insert(make_pair(curr,Node(curr,curr)));
        }
    } 
    //the next collect    
    for(curr_iter = interval_map.begin(); curr_iter != interval_map.end(); curr_iter++)
    {
        int lower = curr_iter->second.lower;
        int higher = curr_iter->second.higher;
        int newlower = lower, newhigher = higher;

        des_iter = interval_map.find(lower - 1);
        if (des_iter != interval_map.end())
        {
            curr_iter->second.lower = des_iter->second.lower;
            newlower = des_iter->second.lower;
        }

        inc_iter = interval_map.find(higher + 1);
        if (inc_iter != interval_map.end()){
            curr_iter->second.higher = inc_iter->second.higher;
            newhigher = inc_iter->second.higher;
        }

        if (des_iter != interval_map.end()){
            des_iter->second.higher = newhigher;
        }
        if (inc_iter != interval_map.end()){
            inc_iter->second.lower = newlower;
        }
        if (curr_iter->second.higher - curr_iter->second.lower + 1> max){
             max = curr_iter->second.higher - curr_iter->second.lower + 1;
         }
    }   
    return max;
}
};