Longest Consecutive Sequence Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/longest-consecutive-sequence

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array of integers A, find the length of the longest consecutive elements sequence.

Naive Approach

The simple solution is to sort the array and find the longest consecutive sequence in the sorted array.

• Initialize the longest sequence as 1.
• Traverse the array from the index 1 to n - 1.
• If the difference between the current element and the previous element is greater than 1 then set the value of the longest sequence as 1.
• Otherwise, if the difference between two consecutive elements is 1, increment the value of the longest sequence by 1 and update the maximum value of the longest sequence.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(1)

Implementation

C++

int longestConsecutiveSequence(vector<int> &A) {
    sort (A.begin(), A.end());
	int currentMaxSequence = 1;
	int ans = 1;
	for (int i = 1; i < A.size(); i++) {
		if (A[i] - A[i - 1] > 1) {
			currentMaxSequence = 1;
		} else {
			if (A[i] - A[i - 1] == 1) {
				currentMaxSequence++;
			}
		}
		ans = max (ans, currentMaxSequence);

	}
	return ans;
}

Java

class Solution {
	int longestConsecutiveSequence(int[] A) {
	    Arrays.sort (A);
		int currentMaxSequence = 1;
		int ans = 1;
		for (int i = 1; i < A.length; i++) {
			if (A[i] - A[i - 1] > 1) {
				currentMaxSequence = 1;
			} else {
				if (A[i] - A[i - 1] == 1) {
					currentMaxSequence++;
				}
			}
			ans = Math.max (ans, currentMaxSequence);

		}
		return ans;
	}
}

Optimal Approach

This problem can be solved efficiently by using a hashmap.

• Create a hashmap, say countAllElements.
• Traverse the array and for every valid i set countAllElements[A[i]] = 1;
• Now again traverse the array and for each element check if the previous element is present in the hashmap.
• If the previous element is present in the hashmap then this element can not be a starting point.
• If the previous element is not present in the hashmap then the current element must be a starting point of a consecutive sequence. Count the number of elements in the current sequence from the hashmap and update the maximum value of the longest sequence.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

int longestConsecutiveSequence(vector<int> &A) {
    unordered_map<int, int> countAllElements;
	int n = A.size();
	for (int i = 0; i < n; i++) {
		countAllElements[A[i]] = 1;
	}
	int ans = 0, currentSequence = 0;
	for (int i = 0; i < n; i++) {
		if (countAllElements[A[i] - 1] == 1) {
		    continue;
		} 
		currentSequence = 0;
		int value = A[i];
		while (countAllElements[value] == 1) {
			currentSequence++;
			value++;
		}
		ans = max (ans, currentSequence);
	}
	return ans;
}

Java

class Solution {
	int longestConsecutiveSequence(int[] A) {
	    HashMap <Integer, Integer> countAllElements = new HashMap<Integer, Integer> ();
		int n = A.length;
		for (int i = 0; i < n; i++) {
			countAllElements.put(A[i], 1);
		}
		int ans = 0, currentSequence = 0;
		for (int i = 0; i < n; i++) {
			if (countAllElements.get(A[i] - 1) != null) {
				continue;
			} 
			currentSequence = 0;
			int value = A[i];
			while (countAllElements.get(value) != null) {
				currentSequence++;
				value++;
			}
			ans = Math.max (ans, currentSequence);
		}
		return ans;
	}
}