Problem Statement: You are given an array of ‘N’ integers. You need to find the length of the longest sequence which contains the consecutive elements.
Examples
Example 1: Input: [100, 200, 1, 3, 2, 4] Output: 4 Explanation: The longest consecutive subsequence is 1, 2, 3, and 4. Input: [3, 8, 5, 7, 6] Output: 4 Explanation: The longest consecutive subsequence is 5, 6, 7, and 8.
Practice:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Brute Force Approach
Algorithm / Intuition
Brute-force Approach:
A straightforward but basic solution is to examine consecutive sequences for each element in the given array. For every element x, we will try to find the consecutive elements, x+1, x+2, x+3, and so on using the linear search algorithm. Thus, we will check the length of the longest consecutive subsequence we can build for every element x. Among all the lengths we will consider the maximum one.
Algorithm:
- To begin, we will utilize a loop to iterate through each element one by one.
- Next, for every element x, we will try to find the consecutive elements like x+1, x+2, x+3, and so on using the linear search algorithm in the given array.
- Within a loop, our objective is to locate the next consecutive element x+1.
- If this element is found, we increment x by 1 and continue the search for x+2.
- Furthermore, we increment the length of the current sequence (cnt) by 1.
- Within a loop, our objective is to locate the next consecutive element x+1.
This process repeats until step 2.2 occurs.
- If a specific consecutive element, for example, x+i, is not found, we will halt the search for subsequent consecutive elements such as x+i+1, x+i+2, and so on. Instead, we will take into account the length of the current sequence (cnt).
- Among all the lengths we get for all the given array elements, the maximum one will be the answer.
Dry-run: Please refer to the video for the dry-run.
Code
#include <bits/stdc++.h>
using namespace std;
bool linearSearch(vector<int>&a, int num) {
int n = a.size(); //size of array
for (int i = 0; i < n; i++) {
if (a[i] == num)
return true;
}
return false;
}
int longestSuccessiveElements(vector<int>&a) {
int n = a.size(); //size of array
int longest = 1;
//pick a element and search for its
//consecutive numbers:
for (int i = 0; i < n; i++) {
int x = a[i];
int cnt = 1;
//search for consecutive numbers
//using linear search:
while (linearSearch(a, x + 1) == true) {
x += 1;
cnt += 1;
}
longest = max(longest, cnt);
}
return longest;
}
int main()
{
vector<int> a = {100, 200, 1, 2, 3, 4};
int ans = longestSuccessiveElements(a);
cout << "The longest consecutive sequence is " << ans << "\n";
return 0;
}
import java.util.*;
public class tUf {
public static boolean linearSearch(int []a, int num) {
int n = a.length; //size of array
for (int i = 0; i < n; i++) {
if (a[i] == num)
return true;
}
return false;
}
public static int longestSuccessiveElements(int []a) {
int n = a.length; //size of array
int longest = 1;
//pick a element and search for its
//consecutive numbers:
for (int i = 0; i < n; i++) {
int x = a[i];
int cnt = 1;
//search for consecutive numbers
//using linear search:
while (linearSearch(a, x + 1) == true) {
x += 1;
cnt += 1;
}
longest = Math.max(longest, cnt);
}
return longest;
}
public static void main(String[] args) {
int[] a = {100, 200, 1, 2, 3, 4};
int ans = longestSuccessiveElements(a);
System.out.println("The longest consecutive sequence is " + ans);
}
}
def linearSearch(a, num):
n = len(a) # size of array
for i in range(n):
if a[i] == num:
return True
return False
def longestSuccessiveElements(a):
n = len(a) # size of array
longest = 1
# pick an element and search for its consecutive numbers
for i in range(n):
x = a[i]
cnt = 1
# search for consecutive numbers using linear search
while linearSearch(a, x + 1):
x += 1
cnt += 1
longest = max(longest, cnt)
return longest
a = [100, 200, 1, 2, 3, 4]
ans = longestSuccessiveElements(a)
print("The longest consecutive sequence is", ans)
function linearSearch(arr, num) {
let n = arr.length; // size of array
for (let i = 0; i < n; i++) {
if (arr[i] === num)
return true;
}
return false;
}
function longestSuccessiveElements(arr) {
let n = arr.length; // size of array
let longest = 1;
// pick an element and search for its
// consecutive numbers:
for (let i = 0; i < n; i++) {
let x = arr[i];
let cnt = 1;
// search for consecutive numbers
// using linear search:
while (linearSearch(arr, x + 1) === true) {
x += 1;
cnt += 1;
}
longest = Math.max(longest, cnt);
}
return longest;
}
let arr = [100, 200, 1, 2, 3, 4];
let ans = longestSuccessiveElements(arr);
console.log("The longest consecutive sequence is", ans);
Output: The longest consecutive sequence is 4.
Complexity Analysis
Time Complexity: O(N2), N = size of the given array.
Reason: We are using nested loops each running for approximately N times.
Space Complexity: O(1), as we are not using any extra space to solve this problem.
Better Approach
Algorithm / Intuition
Better Approach(Using sorting):
We can simply sort the array and run a for loop to find the longest consecutive sequence.
Algorithm:
- We will consider 3 variables,
- ‘lastSmaller’ →(to store the last included element of the current sequence),
- ‘cnt’ → (to store the length of the current sequence),
- ‘longest’ → (to store the maximum length).
- Initialize ‘lastSmaller’ with ‘INT_MIN’, ‘cnt’ with 0, and ‘longest’ with 1(as the minimum length of the sequence is 1).
The steps are as follows:
- First, we will sort the entire array.
- To begin, we will utilize a loop(say i) to iterate through each element one by one.
- For every element, we will check if this can be a part of the current sequence like the following:
- If arr[i]-1 == lastSmaller: The last element in our sequence is labeled as ‘lastSmaller’ and the current element ‘arr[i]’ is exactly ‘lastSmaller’+1. It indicates that ‘arr[i]’ is the next consecutive element. To incorporate it into the sequence, we update ‘lastSmaller’ with the value of ‘arr[i]’ and increment the length of the current sequence, denoted as ‘cnt’, by 1.
- If arr[i] == lastSmaller: If the current element, arr[i], matches the last element of the sequence (represented by ‘lastSmaller’), we can skip it since we have already included it before.
- Otherwise, if lastSmaller != arr[i]: On satisfying this condition, we can conclude that the current element, arr[i] > lastSmaller+1. It indicates that arr[i] cannot be a part of the current sequence. So, we will start a new sequence from arr[i] by updating ‘lastSmaller’ with the value of arr[i]. And we will set the length of the current sequence(cnt) to 1.
- If arr[i]-1 == lastSmaller: The last element in our sequence is labeled as ‘lastSmaller’ and the current element ‘arr[i]’ is exactly ‘lastSmaller’+1. It indicates that ‘arr[i]’ is the next consecutive element. To incorporate it into the sequence, we update ‘lastSmaller’ with the value of ‘arr[i]’ and increment the length of the current sequence, denoted as ‘cnt’, by 1.
- Every time, inside the loop, we will compare ‘cnt’ and ‘longest’ and update ‘longest’ with the maximum value. longest = max(longest, cnt)
- Finally, once the iteration is complete, we will have the answer stored in the variable ‘longest’.
Note: Here, we are distorting the given array by sorting it.
Dry-run: Please refer to the video for the dry-run.
Code
#include <bits/stdc++.h>
using namespace std;
int longestSuccessiveElements(vector<int>&a) {
int n = a.size();
if (n == 0) return 0;
//sort the array:
sort(a.begin(), a.end());
int lastSmaller = INT_MIN;
int cnt = 0;
int longest = 1;
//find longest sequence:
for (int i = 0; i < n; i++) {
if (a[i] - 1 == lastSmaller) {
//a[i] is the next element of the
//current sequence.
cnt += 1;
lastSmaller = a[i];
}
else if (a[i] != lastSmaller) {
cnt = 1;
lastSmaller = a[i];
}
longest = max(longest, cnt);
}
return longest;
}
int main()
{
vector<int> a = {100, 200, 1, 2, 3, 4};
int ans = longestSuccessiveElements(a);
cout << "The longest consecutive sequence is " << ans << "\n";
return 0;
}
import java.util.*;
public class tUf {
public static int longestSuccessiveElements(int []a) {
int n = a.length;
if (n == 0) return 0;
//sort the array:
Arrays.sort(a);
int lastSmaller = Integer.MIN_VALUE;
int cnt = 0;
int longest = 1;
//find longest sequence:
for (int i = 0; i < n; i++) {
if (a[i] - 1 == lastSmaller) {
//a[i] is the next element of the
//current sequence.
cnt += 1;
lastSmaller = a[i];
} else if (a[i] != lastSmaller) {
cnt = 1;
lastSmaller = a[i];
}
longest = Math.max(longest, cnt);
}
return longest;
}
public static void main(String[] args) {
int[] a = {100, 200, 1, 2, 3, 4};
int ans = longestSuccessiveElements(a);
System.out.println("The longest consecutive sequence is " + ans);
}
}
def longestSuccessiveElements(a):
n = len(a)
if n == 0:
return 0
# sort the array
a.sort()
lastSmaller = float('-inf')
cnt = 0
longest = 1
# find longest sequence
for i in range(n):
if a[i] - 1 == lastSmaller:
# a[i] is the next element of the
# current sequence
cnt += 1
lastSmaller = a[i]
elif a[i] != lastSmaller:
cnt = 1
lastSmaller = a[i]
longest = max(longest, cnt)
return longest
a = [100, 200, 1, 2, 3, 4]
ans = longestSuccessiveElements(a)
print("The longest consecutive sequence is", ans)
function longestSuccessiveElements(arr) {
let n = arr.length;
if (n === 0) return 0;
// sort the array:
arr.sort((a, b) => a - b);
let lastSmaller = -Infinity;
let cnt = 0;
let longest = 1;
// find longest sequence:
for (let i = 0; i < n; i++) {
if (arr[i] - 1 === lastSmaller) {
// arr[i] is the next element of the
// current sequence.
cnt += 1;
lastSmaller = arr[i];
} else if (arr[i] !== lastSmaller) {
cnt = 1;
lastSmaller = arr[i];
}
longest = Math.max(longest, cnt);
}
return longest;
}
let arr = [100, 200, 1, 2, 3, 4];
let ans = longestSuccessiveElements(arr);
console.log("The longest consecutive sequence is", ans);
Output: The longest consecutive sequence is 4.
Complexity Analysis
Time Complexity: O(NlogN) + O(N), N = size of the given array.
Reason: O(NlogN) for sorting the array. To find the longest sequence, we are using a loop that results in O(N).
Space Complexity: O(1), as we are not using any extra space to solve this problem.
Optimal Approach
Algorithm / Intuition
Optimal Approach(Using Set data structure):
We will adopt a similar approach to the brute-force method but with optimizations in the search process. Instead of searching sequences for every array element as in the brute-force approach, we will focus solely on finding sequences only for those numbers that can be the starting numbers of the sequences. This targeted approach narrows down our search and improves efficiency.
We will do this with the help of the Set data structure.
How to identify if a number can be the starting number for a sequence:
- First, we will put all the array elements into the set data structure.
- If a number, num, is a starting number, ideally, num-1 should not exist. So, for every element, x, in the set, we will check if x-1 exists inside the set. :
- If x-1 exists: This means x cannot be a starting number and we will move on to the next element in the set.
- If x-1 does not exist: This means x is a starting number of a sequence. So, for number, x, we will start finding the consecutive elements.
How to search for consecutive elements for a number, x:
- Instead of using linear search, we will use the set data structure itself to search for the elements x+1, x+2, x+3, and so on.
Thus, using this method we can narrow down the search and optimize the approach.
Algorithm:
We will declare 2 variables,
- ‘cnt’ → (to store the length of the current sequence),
- ‘longest’ → (to store the maximum length).
- First, we will put all the array elements into the set data structure.
- For every element, x, that can be a starting number(i.e. x-1 does not exist in the set) we will do the following:
- We will set the length of the current sequence(cnt) to 1.
- Then, again using the set, we will search for the consecutive elements such as x+1, x+2, and so on, and find the maximum possible length of the current sequence. This length will be stored in the variable ‘cnt’.
- After that, we will compare ‘cnt’ and ‘longest’ and update the variable ‘longest’ with the maximum value (i.e. longest = max(longest, cnt)).
- Finally, we will have the answer i.e. ‘longest’.
Dry-run: Please refer to the video for the dry-run.
Code
#include <bits/stdc++.h>
using namespace std;
int longestSuccessiveElements(vector<int>&a) {
int n = a.size();
if (n == 0) return 0;
int longest = 1;
unordered_set<int> st;
//put all the array elements into set:
for (int i = 0; i < n; i++) {
st.insert(a[i]);
}
//Find the longest sequence:
for (auto it : st) {
//if 'it' is a starting number:
if (st.find(it - 1) == st.end()) {
//find consecutive numbers:
int cnt = 1;
int x = it;
while (st.find(x + 1) != st.end()) {
x = x + 1;
cnt = cnt + 1;
}
longest = max(longest, cnt);
}
}
return longest;
}
int main()
{
vector<int> a = {100, 200, 1, 2, 3, 4};
int ans = longestSuccessiveElements(a);
cout << "The longest consecutive sequence is " << ans << "\n";
return 0;
}
import java.util.*;
public class tUf {
public static int longestSuccessiveElements(int[] a) {
int n = a.length;
if (n == 0)
return 0;
int longest = 1;
Set<Integer> set = new HashSet<>();
// put all the array elements into set
for (int i = 0; i < n; i++) {
set.add(a[i]);
}
// Find the longest sequence
for (int it : set) {
// if 'it' is a starting number
if (!set.contains(it - 1)) {
// find consecutive numbers
int cnt = 1;
int x = it;
while (set.contains(x + 1)) {
x = x + 1;
cnt = cnt + 1;
}
longest = Math.max(longest, cnt);
}
}
return longest;
}
public static void main(String[] args) {
int[] a = {100, 200, 1, 2, 3, 4};
int ans = longestSuccessiveElements(a);
System.out.println("The longest consecutive sequence is " + ans);
}
}
def longestSuccessiveElements(a):
n = len(a)
if n == 0:
return 0
longest = 1
st = set()
# put all the array elements into set
for i in range(n):
st.add(a[i])
# Find the longest sequence
for it in st:
# if 'it' is a starting number
if it - 1 not in st:
# find consecutive numbers
cnt = 1
x = it
while x + 1 in st:
x += 1
cnt += 1
longest = max(longest, cnt)
return longest
a = [100, 200, 1, 2, 3, 4]
ans = longestSuccessiveElements(a)
print("The longest consecutive sequence is", ans)
function longestSuccessiveElements(a) {
let n = a.length;
if (n === 0)
return 0;
let longest = 1;
let st = new Set();
// put all the array elements into set
for (let i = 0; i < n; i++) {
st.add(a[i]);
}
// Find the longest sequence
for (let it of st) {
// if 'it' is a starting number
if (!st.has(it - 1)) {
// find consecutive numbers
let cnt = 1;
let x = it;
while (st.has(x + 1)) {
x = x + 1;
cnt = cnt + 1;
}
longest = Math.max(longest, cnt);
}
}
return longest;
}
let a = [100, 200, 1, 2, 3, 4];
let ans = longestSuccessiveElements(a);
console.log("The longest consecutive sequence is", ans);
Output: The longest consecutive sequence is 4.
Complexity Analysis
Time Complexity: O(N) + O(2*N) ~ O(3*N), where N = size of the array.
Reason: O(N) for putting all the elements into the set data structure. After that for every starting element, we are finding the consecutive elements. Though we are using nested loops, the set will be traversed at most twice in the worst case. So, the time complexity is O(2*N) instead of O(N2).
Space Complexity: O(N), as we are using the set data structure to solve this problem.
Note: The time complexity is computed under the assumption that we are using unordered_set and it is taking O(1) for the set operations.
- If we consider the worst case the set operations will take O(N) in that case and the total time complexity will be approximately O(N2).
- And if we use the set instead of unordered_set, the time complexity for the set operations will be O(logN) and the total time complexity will be O(NlogN).
Video Explanation
Special thanks to Nishant Rana, Sudip Ghosh and KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article