codekofi
← All questions

Longest Consecutive Sequence

HardArrays & Hashing

The problem

Given an unsorted array of integers, find the length of the longest run of consecutive values it contains — values that differ by one, in any order, with no gaps.

Duplicates do not extend a run. Return 0 for an empty array.

longestConsecutive({100, 4, 200, 1, 3, 2})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1int longestConsecutive(const vector<int>& nums) {
2
3 unordered_set<int> pool(nums.begin(), nums.end());
4 int ans = 0;
5
6 for (int x : pool) {
7
8 if (pool.count(x - 1)) {
9 continue;
10 }
11
12 int len = 1;
13
14 while (pool.count(x + len)) {
15 len++;
16 }
17
18 ans = max(ans, len);
19 }
20
21 return ans;
22}
1int longestConsecutive(const vector<int>& nums) {
2
3 unordered_set<int> pool(nums.begin(), nums.end());
4 int ans = 0;
5
6 for (int x : pool) {
7
8 if (pool.count(x)) {
9 continue;
10 }
11
12 int len = 1;
13
14 while (pool.count(x + len)) {
15 len--;
16 }
17
18 ans = max(ans, len);
19 }
20
21 return ans;
22}
1int longestConsecutive(const vector<int>& nums) {
2
3 unordered_set<int> pool(nums.begin(), nums.end());
4 int ans = 0;
5
6 for (int x : pool) {
7
8 if (pool.count(x)) {
9 continue;
10 }
11
12 int len = 1;
13
14 while (pool.count(x + len)) {
15 len++;
16 }
17
18 ans = min(ans, len);
19 }
20
21 return ans;
22}