## Monday, October 27, 2014

### LeetCode OJ - Longest Consecutive Sequence

Problem:

Solution:

Apparently one can sort the sequence and walk it to see the longest consecutive sequence. The challenge is to do it faster than that. The sorting algorithm takes $O(n \log n)$ time, so to get faster let's aim at $O(n)$. In fact the problem requires that.

If we scan the sequence element 1 by 1, then we can only spend constant time on each element. My idea is to build the consecutive chains. We keep track of all consecutive sequences so far and try to grow them, for the input example, here are the states:

Initially, we have

 Unread input: 100, 4, 200, 1, 3, 2 Sequences: []

By reading the first input, then we have

 Unread input: 100, 4, 200, 1, 3, 2 Sequences: [{100}]

Similarly, we also have

 Unread input: 100, 4, 200, 1, 3, 2 Sequences: [{100}, {4}]

 Unread input: 100, 4, 200, 1, 3, 2 Sequences: [{100}, {4}, {200} ]

 Unread input: 100, 4, 200, 1, 3, 2 Sequences: [{100}, {4}, {200}, {1} ]

So finally we see something interesting here, instead of creating {3} as a new sequence, we should join it with the sequence {4} to form {3, 4}

 Unread input: 100, 4, 200, 1, 3, 2 Sequences: [{100}, {3, 4}, {200}, {1} ]

The next move is even more interesting, we will join {1} and {3, 4} using 2 and form {1, 2, 3, 4}

 Unread input: 100, 4, 200, 1, 3, 2 Sequences: [{100}, {1, 2, 3, 4}, {200}]

And so the finally answer is 4. The basic operation in this algorithm relies on the ability to quickly locate the right sequence to join. To save time, I used map to find those sequences, and that will take $O(\log n)$ in the worst case, not great, but if I use hash, then I will get an expected $O(n)$ algorithm!

Code:

#include "stdafx.h"

// https://oj.leetcode.com/problems/longest-consecutive-sequence/

#include "LEET_LONGEST_CONSECUTIVE_SEQUENCE.h"

#include <vector>
#include <set>
#include <map>
#include <iostream>

using namespace std;

namespace _LEET_LONGEST_CONSECUTIVE_SEQUENCE
{
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 (unsigned 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);

if (peekStart != startChain.end() && peekEnd != endChain.end())
{
// Attachable to the start and attachable to the 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));
}
else if (peekStart != startChain.end() && peekEnd == endChain.end())
{
// Attachable to the start only
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));
}
else if (peekStart == startChain.end() && peekEnd != endChain.end())
{
// Attachable to the end only
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));
}
else if (peekStart == startChain.end() && peekEnd == endChain.end())
{
// Nothing else could be done - create a chain by itself
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;
}
};
};

using namespace _LEET_LONGEST_CONSECUTIVE_SEQUENCE;

int LEET_LONGEST_CONSECUTIVE_SEQUENCE()
{
Solution solution;
vector<int> nums;
// 100, 4, 200, 1, 3, 2
nums.push_back(100);
nums.push_back(4);
nums.push_back(200);
nums.push_back(1);
nums.push_back(3);
nums.push_back(2);
cout << solution.longestConsecutive(nums) << endl;
return 0;
}