Measure the Longest Consecutive Value Run in Linear Time
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return the length of the longest run of consecutive integer values present in an unsorted array. The values need not be adjacent in the input. Repeated copies of a value do not extend a run. Your algorithm must run in `O(n)` time.
```cpp
int longestConsecutive(vector<int>& nums);
```
### Examples
```text
Input: nums = [12,4,9,6,5,4,7]
Output: 4
```
The run is 4,5,6,7.
```text
Input: nums = []
Output: 0
```
### Constraints
- The length is between 0 and 100000.
- Each value lies between -1000000000 and 1000000000, inclusive.
Overview: Find the longest present consecutive-value run with a deterministic fixed-width linear-time construction.
Community answers
Answer by Coderka14
#include
using namespace std;
class Solution
{
public:
int longestConsecutive(vector& nums)
{
unordered_set st(nums.begin(), nums.end());
int longest = 0;
for (int x : st)
{
if (st.find(x - 1) != st.end())
{
continue;
}
int current = x;
int length = 1;
while (current != INT_MAX && st.find(current + 1) != st.end())
{
current++;
length++;
}
longest = max(longest, length);
}
return longest;
}
};