Find Longest Consecutive Sequence Length
Hard
C++
Arrays
34 views
Problem Statement
Find length of longest sequence of consecutive numbers that can be formed from array elements. This teaches set-based thinking.
Logic: For each number, check if it's start of sequence, then count length
Logic: For each number, check if it's start of sequence, then count length
Input Format
An integer n (size of array)
Then n integers.
Then n integers.
Output Format
Length of the longest consecutive sequence.
Example
6 100 4 200 1 3 2
4
Constraints
• n ≥ 1
• Elements can be in any order
• Use set / unordered_set
• Elements can be in any order
• Use set / unordered_set
Concept Explanation
Consecutive sequence means numbers like 1, 2, 3, 4 without gaps.
Order in array does not matter.
Order in array does not matter.
Step-by-Step Explanation
1.Insert all array elements into a set (or unordered_set).
2.Initialize longest = 0.
3.For each number x in the array:
4.Check if (x - 1) is not present in the set.
• If not present, x is the start of a sequence.
5.Start counting from x:
• While (x + 1) exists in the set, increase count and move to next number.
6.Update longest with the maximum count found.
7.After checking all numbers, print longest.
2.Initialize longest = 0.
3.For each number x in the array:
4.Check if (x - 1) is not present in the set.
• If not present, x is the start of a sequence.
5.Start counting from x:
• While (x + 1) exists in the set, increase count and move to next number.
6.Update longest with the maximum count found.
7.After checking all numbers, print longest.
Concept Explanation
Consecutive sequence means numbers like 1, 2, 3, 4 without gaps.
Order in array does not matter.
Order in array does not matter.
Step-by-Step Explanation
1.Insert all array elements into a set (or unordered_set).
2.Initialize longest = 0.
3.For each number x in the array:
4.Check if (x - 1) is not present in the set.
• If not present, x is the start of a sequence.
5.Start counting from x:
• While (x + 1) exists in the set, increase count and move to next number.
6.Update longest with the maximum count found.
7.After checking all numbers, print longest.
2.Initialize longest = 0.
3.For each number x in the array:
4.Check if (x - 1) is not present in the set.
• If not present, x is the start of a sequence.
5.Start counting from x:
• While (x + 1) exists in the set, increase count and move to next number.
6.Update longest with the maximum count found.
7.After checking all numbers, print longest.
Input / Output Format
Input Format
An integer n (size of array)
Then n integers.
Then n integers.
Output Format
Length of the longest consecutive sequence.
Constraints
• n ≥ 1
• Elements can be in any order
• Use set / unordered_set
• Elements can be in any order
• Use set / unordered_set
Examples
Input:
6
100 4 200 1 3 2
Output:
4
Example Solution (Public)
void question14_longest_consecutive() {
int arr[] = {100, 4, 200, 1, 3, 2};
int size = 6;
int maxLength = 0;
for(int i = 0; i < size; i++) {
int current = arr[i];
int length = 1;
// Check if current is start of sequence
bool isStart = true;
for(int j = 0; j < size; j++) {
if(arr[j] == current - 1) {
isStart = false;
break;
}
}
if(isStart) {
while(true) {
bool found = false;
for(int j = 0; j < size; j++) {
if(arr[j] == current + 1) {
length++;
current++;
found = true;
break;
}
}
if(!found) break;
}
if(length > maxLength) {
maxLength = length;
}
}
}
cout << "Longest consecutive sequence length: " << maxLength << endl;
}
Official Solution Code
void question14_longest_consecutive() {
int arr[] = {100, 4, 200, 1, 3, 2};
int size = 6;
int maxLength = 0;
for(int i = 0; i < size; i++) {
int current = arr[i];
int length = 1;
// Check if current is start of sequence
bool isStart = true;
for(int j = 0; j < size; j++) {
if(arr[j] == current - 1) {
isStart = false;
break;
}
}
if(isStart) {
while(true) {
bool found = false;
for(int j = 0; j < size; j++) {
if(arr[j] == current + 1) {
length++;
current++;
found = true;
break;
}
}
if(!found) break;
}
if(length > maxLength) {
maxLength = length;
}
}
}
cout << "Longest consecutive sequence length: " << maxLength << endl;
}
Please login to submit solutions.