LeeCode: 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.

Analysis:

This is a typical problem to solve by sacrificing space to buy time. Since it is required O(n) complexity, we cannot simply sort it with common sorting algorithms. Borrowed the smart idea of using two unordered_map (representing a range with first and last) and the most neat coding style:

	int longestConsecutive(vector<int> &num) {
	if(num.size()==0) return 0;
	unordered_map<int, int> mapF2L;//map linking first to last
	unordered_map<int, int> mapL2F;//map linking last to first
	int maxLen = 0;
	for(int val : num){
	int first = val, last = val+1; //represent a range with[first, last)
	if(mapF2L.find(first) != mapF2L.end() || mapL2F.find(last) != mapL2F.end())
	// if the current element is duplicated
	continue;
	//check if current first is the last of an existing range
	auto rangeL2F = mapL2F.find(first);
	if(rangeL2F!= mapL2F.end()){
	first = rangeL2F->second;
	mapL2F.erase(rangeL2F);
	}
	//check if current last is the first of an existing range
	auto rangeF2L = mapF2L.find(last);
	if(rangeF2L!=mapF2L.end()){
	last = rangeF2L->second;
	mapF2L.erase(rangeF2L);
	}
	mapF2L[first]=last;
	mapL2F[last]=first;
	maxLen = max(maxLen, last-first);
	}
	return maxLen;
	}

view raw gistfile1.cpp hosted with ❤ by GitHub