C++: Find Longest Sequence of Numbers in An Unsorted Array

Given an unsorted array, find the length of the longest sequence of consecutive numbers in the array.

#include <bits/stdc++.h>
using namespace std;
int findSequence(vector<int> v) {
unordered_set<int> hashSet;
for(auto i = v.begin(); i != v.end(); i++) {
hashSet.insert(*i);
}
int length = 0;
int max = 0;
for(auto i = v.begin(); i != v.end(); i++) {
if (hashSet.find(*i - 1) != hashSet.end()) {
continue;
}
int start = *i;
while (hashSet.find(start++) != hashSet.end()) {
length++;
}
if (length > max) {
max = length;
length = 0;
}
}
return max;
}
int main() {
vector<int> v = {1,4,5,6,3};
cout << findSequence(v) << endl;
return 0;
}
$ g++ -std=c++11 ./FindLongestSequence.cc
$ ./a.out
4

Reference

Written with StackEdit.

BlinkBlank

Knowledge is the seed of wisdom.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.