# Is my solution O(n) time/space? With linked list.

• I create Sequence elements telling the FIRST and LAST element of the sequence, sorting them in a linked list.

For each input number:

• scroll the sequence list as far as the input is LESS than next sequence (or end of list) (while).
• check if the input is in the current sequence (continue)
• if extends both, merge
• else if extends one, update bound
• else there's no extension at all, so add new sequence (one element)

In the meanwhile:
At every sequence change update maxSeqLength

``````class Solution {

struct Sequence {
int first;
int last;
Sequence* next;

Sequence(int aFirst, int aLast)
: first(aFirst), last(aLast), next(NULL) {}

~Sequence() { if (next) delete next; }
};

public:
int longestConsecutive(vector<int> &num) {
int maxSeqLength = 0;
vector<int>::iterator it = num.begin();
int minInt = std::numeric_limits<int>::min();

while(it != num.end())
{
int val = *it++;

// Scroll list when val > next_sequence_first
{
}
// Skip if already contained in next or previous sequence
{
continue;
}
// Check if expands previous sequence (high bound) or next sequence (low bound)
bool bExpandPrevious = (head->last  == val - 1 );

// it can happen we've got a value that merges two sequences
if (bExpandPrevious && bExpandNext)
{
//Merge
pTemp->next = NULL;

delete pTemp;
}
else if (bExpandPrevious)    // or expands previous only
{
//Update last
}
else if (bExpandNext)       // or expands last only
{
// Update first
}
else                        // or it's a brand new sequence (of 1 element!)
{
// insert in between
}
}
return maxSeqLength;
}
};``````

• You used two linked lists to represent the first and last element in sequence, so every time you meet a new element, you need to go through the two lists, which is O(n). So actually, your algorithm is o(n^2). You should use Hash map to speed it up. The search operation of hash is only O(1), so your algorithm will be O(n).

• I think I am actually using one list with two values per node (low and high of a sequence).
For each new element I go through the one list to update the list itself and the maxSequenceLength counter. Where does it look like two lists?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.