Skip to content

Instantly share code, notes, and snippets.

@anhdiepmmk
Last active July 1, 2022 06:57
Show Gist options
  • Save anhdiepmmk/31e3d23e4a9274c7f293adc2d7459184 to your computer and use it in GitHub Desktop.
Save anhdiepmmk/31e3d23e4a9274c7f293adc2d7459184 to your computer and use it in GitHub Desktop.
Longest Consecutive Subsequence
/*
Given an unsorted array of integersarr, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input:arr = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input:arr = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints:
0 <=arr.length <= 105
-109 <=arr[i] <= 109
*/
const sortNumbers = (numbers) => {
for (let i = 0; i < numbers.length - 1; i++) {
for (let j = i + 1; j < numbers.length; j++) {
if (numbers[i] > numbers[j]) {
const tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
}
}
};
const countLongestConsecutiveSequence = (numbers) => {
let current = 0;
let longest = 0;
for (let i = 0; i <= numbers.length; i++) {
const currentValue = numbers[i];
const previousValue = numbers[i - 1] + 1;
if (i > 0 && currentValue === previousValue) {
current++;
} else {
current = 1;
}
longest = Math.max(longest, current);
}
return longest;
};
const numbers = [
0, 1, 2, 2, 3, 9, 10, 11, 12, 13, 14, 15, 16, 1, 2, 3, 4, 5, 6, 9, 10, 15, 0,
17,
];
sortNumbers(numbers);
const result = countLongestConsecutiveSequence(numbers);
console.log(result);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment