Longest Consecutive Sequence

/*

Longest Consecutive Sequence

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 elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
*/
//limitation on max size and offset
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        if(size == 0) return 0;
        if(size == 1) return 1;
        vector<bool> indicator;
       
        int offset = 2000;
        int maxSize = 20000;
       
        int i;
        for(i=0; i<maxSize; i++){
          indicator.push_back(false);
        }
       
        for(i=0; i<size; i++){
          if((num[i]+offset) >= maxSize || (num[i]+offset) < 0) return -1;
          indicator[num[i]+offset] = true;
        }
       
        int pos = 0;
        int result = 1;
        int tempResult = 0;
       
        while(pos < maxSize){
          if((pos == 0 && indicator[pos] == true)
             ||(pos > 1 && indicator[pos-1] == false && indicator[pos] == true)){
             tempResult = 1;
          }
          else if(pos > 1 && indicator[pos-1] == true && indicator[pos] == false){
             result = max(result, tempResult);
          }
          else if(pos > 1 && indicator[pos-1] == true && indicator[pos] == true){
             tempResult++;
          }
          pos++;
        }
       
        if(indicator[maxSize-1] == true) result = max(result, tempResult);
       
        return result;
    }
};


/*
set and hash-table
*/
class Solution {

public:

int longestConsecutive(vector<int> &num)



{
  set<int> seen; // A set keeping track of whether a number is seen or not

map<int, int> startChain; // A map from the starting number to the chain size

map<int, int> endChain; // A map from the ending number to the chain size

for (int i = 0; i < num.size(); i++)



{
  int value = num[i];

if (seen.find(value) == seen.end())



{

seen.insert(value);
  map<int, int>::iterator peekStart = startChain.find(value + 1);

map<int, int>::iterator peekEnd = endChain.find(value - 1);




  // Attachable to the start and attachable to the end

if (peekStart != startChain.end() && peekEnd != endChain.end())



{
  int newStart = peekEnd->first - peekEnd->second + 1;

int newLength = peekEnd->second + 1 + peekStart->second;

int newEnd = newStart + newLength - 1;



startChain.erase(startChain.find(newStart));

endChain.erase(peekEnd);

startChain.erase(peekStart);

endChain.erase(endChain.find(newEnd));
  startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}
  // Attachable to the start only

if (peekStart != startChain.end() && peekEnd == endChain.end())



{
  int newStart = peekStart->first - 1;

int newLength = peekStart->second + 1;

int newEnd = newStart + newLength - 1;



startChain.erase(peekStart);

endChain.erase(endChain.find(newEnd));
  startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}
  // Attachable to the end only

if (peekStart == startChain.end() && peekEnd != endChain.end())



{
  int newEnd = peekEnd->first + 1;

int newLength = peekEnd->second + 1;

int newStart = newEnd - newLength + 1;



startChain.erase(startChain.find(newStart));

endChain.erase(peekEnd);
  startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}
  // Nothing else could be done - create a chain by itself

if (peekStart == startChain.end() && peekEnd == endChain.end())



{
  int newStart = value;

int newEnd = value;

int newLength = 1;

startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}

}

}
  int max = 0;

for (map<int, int>::iterator startIterator = startChain.begin(); startIterator != startChain.end(); startIterator++)



{
  int current = startIterator->second;

if (current > max)



{

max = current;

}

}
  return max;



}

};