Description:
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Examples:
Example 1:
Input: nums = [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: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9Solution in Python:
To solve the problem of finding the length of the longest consecutive elements sequence in an unsorted array in O(n) time, we can use a hash set for efficient lookups and to avoid repeatedly sorting the array. Here’s a detailed explanation and the corresponding Python implementation:
Approach:
- Edge Case:
- If the input array
numsis empty, return 0 since there are no elements to form a sequence.
- If the input array
- Use a Hash Set:
- Insert all the elements of the array into a hash set. This allows for O(1) average time complexity for lookups, which is crucial for achieving the O(n) overall time complexity.
- Find the Longest Sequence:
- Iterate through each element in the array.
- For each element, check if it is the start of a sequence (i.e.,
num - 1is not in the hash set). - If it is the start of a sequence, initialize a counter and incrementally check for the next elements in the sequence (
num + 1,num + 2, etc.). - Keep track of the maximum length of any sequence found.
Python
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
# If the input list is empty, return 0
if not nums:
return 0
# Create a set of all elements in nums for O(1) look-up times
num_set = set(nums)
longest_streak = 0
# Iterate over each number in the array
for num in nums:
# Check if this number is the start of a sequence
if num - 1 not in num_set:
# This number is the start of a sequence
current_num = num
current_streak = 1
# Check the length of the sequence starting with this number
while current_num + 1 in num_set:
current_num += 1
current_streak += 1
# Update the longest streak found so far
longest_streak = max(longest_streak, current_streak)
return longest_streakExplanation:
- Edge Case Handling:
- The check
if not numsensures that if the input list is empty, the function returns 0 immediately.
- The check
- Hash Set Creation:
num_set = set(nums)converts the input list to a hash set, enabling O(1) average time complexity for element lookups.
- Main Loop:
- The loop
for num in numsiterates over each element in the input list. - The condition
if num - 1 not in num_setchecks if the current number is the start of a sequence. This ensures we only start counting sequences from the smallest number in the sequence.
- The loop
- Sequence Counting:
- When a sequence start is identified,
current_numandcurrent_streakare initialized. - The
whileloopwhile current_num + 1 in num_setcounts the length of the sequence by checking for consecutive numbers.
- When a sequence start is identified,
- Update Longest Streak:
longest_streak = max(longest_streak, current_streak)updates the longest streak found so far.
This approach ensures that the algorithm runs in O(n) time, making it efficient for large inputs.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
// If the input array is empty, return 0
if (nums.length === 0) {
return 0;
}
// Create a set of all elements in nums for O(1) look-up times
const numSet = new Set(nums);
let longestStreak = 0;
// Iterate over each number in the array
for (let num of nums) {
// Check if this number is the start of a sequence
if (!numSet.has(num - 1)) {
// This number is the start of a sequence
let currentNum = num;
let currentStreak = 1;
// Check the length of the sequence starting with this number
while (numSet.has(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
// Update the longest streak found so far
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
};Solution in Java:
Java
import java.util.HashSet;
class Solution {
public int longestConsecutive(int[] nums) {
// If the input array is empty, return 0
if (nums.length == 0) {
return 0;
}
// Create a set of all elements in nums for O(1) look-up times
HashSet<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
int longestStreak = 0;
// Iterate over each number in the array
for (int num : nums) {
// Check if this number is the start of a sequence
if (!numSet.contains(num - 1)) {
// This number is the start of a sequence
int currentNum = num;
int currentStreak = 1;
// Check the length of the sequence starting with this number
while (numSet.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
// Update the longest streak found so far
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public int LongestConsecutive(int[] nums) {
// If the input array is empty, return 0
if (nums.Length == 0) {
return 0;
}
// Create a set of all elements in nums for O(1) look-up times
HashSet<int> numSet = new HashSet<int>(nums);
int longestStreak = 0;
// Iterate over each number in the array
foreach (int num in nums) {
// Check if this number is the start of a sequence
if (!numSet.Contains(num - 1)) {
// This number is the start of a sequence
int currentNum = num;
int currentStreak = 1;
// Check the length of the sequence starting with this number
while (numSet.Contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
// Update the longest streak found so far
longestStreak = Math.Max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}