9. Longest consecutive sequence
Here is a list of solutions to the Longest Consecutive Subsequence problem on LeetCode, starting from brute force to the most optimal solution, including code and explanations:
Problem Statement:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
- The sequence must contain consecutive numbers, and the order of numbers in the array does not matter.
- Example:
Input:nums = [100, 4, 200, 1, 3, 2]
Output:4(because the longest consecutive sequence is[1, 2, 3, 4])
1. Brute Force Solution (O(n²) Time, O(1) Space)
This solution involves comparing every number with every other number and forming sequences manually.
Approach:
- Loop through the array.
- Start a sequence for each number.
- For each element, check if the next consecutive element exists by looping again over the array.
- Track the maximum length of any such sequence.
Code (Java):
public class LongestConsecutiveSubsequence {
public static int longestConsecutive(int[] nums) {
int n = nums.length;
int maxLength = 0;
for (int i = 0; i < n; i++) {
int currentNum = nums[i];
int length = 1;
for (int j = 0; j < n; j++) {
if (nums[j] == currentNum + 1) {
length++;
currentNum++;
}
}
maxLength = Math.max(maxLength, length);
}
return maxLength;
}
}Time Complexity: O(n²)
Space Complexity: O(1)
2. Sorting-Based Approach (O(n log n) Time, O(1) Space)
This approach involves sorting the array and then finding consecutive sequences in the sorted array.
Approach:
- Sort the input array.
- Traverse the sorted array to find sequences of consecutive numbers.
- Skip duplicate numbers during traversal.
- Track the length of the longest consecutive subsequence.
Code (Java):
import java.util.Arrays;
public class LongestConsecutiveSubsequence {
public static int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) return 0;
Arrays.sort(nums);
int maxLength = 1;
int currentLength = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1] + 1) {
currentLength++;
} else if (nums[i] != nums[i - 1]) {
currentLength = 1; // Reset if no consecutive sequence
}
maxLength = Math.max(maxLength, currentLength);
}
return maxLength;
}
}Time Complexity: O(n log n) (due to sorting)
Space Complexity: O(1) (ignoring sorting overhead)
3. HashSet Solution (Optimal, O(n) Time, O(n) Space)
This is an efficient solution using a HashSet to store the numbers and check for sequence starts.
Approach:
- Add all numbers to a HashSet to allow for quick lookups.
- Iterate through the array, and for each number
num, check ifnum - 1is not in the set (this meansnumis the start of a sequence). - From this number, count how many consecutive numbers are present in the set.
- Track the length of the longest sequence.
Code (Java):
import java.util.HashSet;
public class LongestConsecutiveSubsequence {
public static int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) return 0;
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLength = 0;
for (int num : set) {
if (!set.contains(num - 1)) { // Start of a sequence
int currentNum = num;
int currentLength = 1;
while (set.contains(currentNum + 1)) {
currentNum++;
currentLength++;
}
maxLength = Math.max(maxLength, currentLength);
}
}
return maxLength;
}
}Time Complexity: O(n)
Space Complexity: O(n)
4. Union-Find (Disjoint Set) Solution (O(n) Time, O(n) Space)
This is an advanced solution using Union-Find (Disjoint Set Union) to group consecutive numbers and find the longest sequence.
Approach:
- Create a Union-Find structure to connect numbers that are part of the same consecutive sequence.
- Union adjacent numbers (
numandnum + 1). - Use the
findfunction to get the representative parent of each number and track the size of each group. - Return the largest group size.
Code (Java):
import java.util.HashMap;
public class LongestConsecutiveSubsequence {
private HashMap<Integer, Integer> parent = new HashMap<>();
private HashMap<Integer, Integer> rank = new HashMap<>();
public int find(int num) {
if (parent.get(num) != num) {
parent.put(num, find(parent.get(num))); // Path compression
}
return parent.get(num);
}
public void union(int num1, int num2) {
int root1 = find(num1);
int root2 = find(num2);
if (root1 != root2) {
if (rank.get(root1) > rank.get(root2)) {
parent.put(root2, root1);
} else if (rank.get(root1) < rank.get(root2)) {
parent.put(root1, root2);
} else {
parent.put(root2, root1);
rank.put(root1, rank.get(root1) + 1);
}
}
}
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) return 0;
for (int num : nums) {
if (!parent.containsKey(num)) {
parent.put(num, num);
rank.put(num, 0);
}
if (parent.containsKey(num - 1)) {
union(num, num - 1);
}
if (parent.containsKey(num + 1)) {
union(num, num + 1);
}
}
int maxLength = 0;
HashMap<Integer, Integer> groupSize = new HashMap<>();
for (int num : nums) {
int root = find(num);
groupSize.put(root, groupSize.getOrDefault(root, 0) + 1);
maxLength = Math.max(maxLength, groupSize.get(root));
}
return maxLength;
}
}Time Complexity: O(n)
Space Complexity: O(n)
Summary of Solutions:
| Approach | Time Complexity | Space Complexity | Explanation |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Compare all pairs manually |
| Sorting-Based | O(n log n) | O(1) | Sort and find sequences |
| HashSet (Optimal) | O(n) | O(n) | Use HashSet to track consecutive starts |
| Union-Find (Optimal) | O(n) | O(n) | Use Union-Find to group and track consecutive numbers |
For coding interviews, the HashSet solution is generally the most recommended due to its simplicity, efficiency, and intuitive logic.