128. Longest Consecutive Sequence
Problem Description
The problem asks us to find the length of the longest sequence of consecutive numbers in an unsorted array called nums
. A sequence of numbers is considered consecutive if every number follows the previous one without any gaps. For example, [1, 2, 3]
is a consecutive sequence, but [1, 3, 4]
is not. Our task is to find the longest such sequence in the given array.
The tricky part of this problem is that we need to come up with a solution that has a time complexity of O(n)
. This means we cannot afford the luxury of sorting the array as it would typically require O(n * log n)
time. Thus, we must find a way to keep track of sequences efficiently, despite the order of elements being arbitrary.
Intuition
To solve this problem in O(n)
time, we need to think of a data structure that allows us to quickly check if an element exists in the set and if we can extend a consecutive sequence. A hash table, or in Python a set, is an ideal candidate because it allows us to query the existence of an element in constant O(1)
time.
Here's the intuition for the solution approach:
-
Convert the
nums
array into a set to eliminate duplicates and allow forO(1)
existence checks. It takesO(n)
time to convert the list to a set. -
We iterate through each number
x
in the original array. For eachx
, we have two conditions:- If
x - 1
is not in the set,x
could be the start of a new sequence. - If
x - 1
is in the set,x
is part of a sequence that started beforex
and we don't need to check it as it will already be covered when we check the beginning of its sequence.
- If
-
When we find a number
x
that is the start of a new sequence (becausex - 1
is not in the set), we then proceed to check how long this sequence is by continuously incrementingy
(initialized asx + 1
) as long asy
is present in the set. -
Each time we extend the sequence, we update the length of the current sequence and update the answer
ans
if the current sequence is longer than the previously recorded longest sequence.
This approach guarantees we only make a constant number of passes through the array and that we only consider each sequence from its beginning, ensuring our algorithm runs in O(n)
time.
Learn more about Union Find patterns.
Solution Approach
The solution approach can be decomposed into key steps that align with the algorithmic design and utilize data structures such as hash tables effectively.
Step 1: Building a Set
Firstly, we convert the given list nums
into a set s
. This process removes any duplicate elements and facilitates constant time checks for the presence of integers. This is critical as it allows for the linear time algorithm we're aiming for.
s = set(nums)
Step 2: Iteration and Sequence Detection
We iterate through each number x
in the list nums
. For each number, we check if its predecessor (x - 1
) is in the set.
for x in nums: if x - 1 not in s:
If x - 1
is not in the set, it implies that x
could potentially be the start of a new consecutive sequence.
Step 3: Extension of the Sequence
When we find that x
could be the start of a sequence, we try to find out where the sequence ends. We initialize a variable y
as x + 1
and while y
is in the set, we keep incrementing y
by one to extend the sequence.
y = x + 1 while y in s: y += 1
Step 4: Update Longest Sequence Length
After we find a sequence starting with x
and ending before y
, the length of this sequence is y - x
. If this length is greater than any previously found sequences, we update our answer ans
.
ans = max(ans, y - x)
Step 5: Return the Result
Once we've considered each number in the array, we return ans
as the answer to the problem, which represents the length of the longest consecutive elements sequence found.
This approach takes advantage of the hash table pattern via the set s
, which provides us with the constant time lookups needed to achieve an overall O(n)
time complexity. Thus, we harness the capability of hash tables to manage our computations efficiently and satisfy the problem's constraints.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Consider the unsorted array nums = [4, 1, 3, 2, 6]
. Our goal is to find the longest sequence of consecutive numbers in this array.
Step 1: Building a Set
We transform the nums
array into a set:
s = set([4, 1, 3, 2, 6]) # s = {1, 2, 3, 4, 6}
Duplications are removed and we can check for existence in constant time.
Step 2: Iteration and Sequence Detection
We iterate through nums
. Assume our iteration order is the same as the array's order.
Iteration 1: x = 4
- We check if
3
(x - 1
) is in the set:
if 3 not in s: # False, hence we skip
Since 3
is present, 4
is not the start of a new sequence.
Iteration 2: x = 1
- We check if
0
(x - 1
) is in the set:
if 0 not in s: # True, thus 1 might be a sequence start
Since 0
is not present, 1
is a start of a new sequence.
Step 3: Extension of the Sequence
We extend the sequence from 1
onwards to find its length:
y = 2 while y in s: y += 1 # y becomes 3, then 4, stops at 5
The sequence we found is 1, 2, 3, 4
.
Step 4: Update Longest Sequence Length
We calculate the length of the current sequence 4 - 1
which is 3
.
ans = max(ans, 4 - 1) # if ans was 0, it becomes 3
We update ans
to the length of this sequence if it is the longest found so far.
Iterations continue with 2
, 3
, and 6
but no other new sequence is found with a length greater than 3
.
Step 5: Return the Result
After iterating through all numbers, the longest sequence found is from 1
to 4
, which has a length of 4
. Thus, ans = 4
and is returned as the solution.
Solution Implementation
1class Solution:
2 def longestConsecutive(self, nums: List[int]) -> int:
3 # Create a set from the list for O(1) lookups
4 num_set = set(nums)
5 longest_streak = 0
6
7 # Iterate over each number in the list
8 for number in nums:
9 # Check if it's the start of a sequence
10 if number - 1 not in num_set:
11 # Initialize the current number as the possible start of a sequence
12 current_num = number
13 current_streak = 1
14
15 # Increment the current_num to find the length of the streak
16 while current_num + 1 in num_set:
17 current_num += 1
18 current_streak += 1
19
20 # Update the longest_streak with the maximum streak found
21 longest_streak = max(longest_streak, current_streak)
22
23 # Return the length of the longest consecutive sequence
24 return longest_streak
25
1class Solution {
2 public int longestConsecutive(int[] nums) {
3 // Create a hash set to store the unique elements of the array.
4 Set<Integer> numSet = new HashSet<>();
5
6 // Add all elements to the set.
7 for (int num : nums) {
8 numSet.add(num);
9 }
10
11 // Initialize the variable for the longest consecutive sequence.
12 int longestStreak = 0;
13
14 // Go through each element in the array.
15 for (int num : nums) {
16 // Check if current number is the beginning of a sequence.
17 if (!numSet.contains(num - 1)) {
18 // Initialize the current number as the potential start of the sequence.
19 int currentNum = num;
20 // Initialize the current streak length.
21 int currentStreak = 1;
22
23 // Expand the current streak if consecutive numbers are found.
24 while (numSet.contains(currentNum + 1)) {
25 currentNum += 1;
26 currentStreak += 1;
27 }
28
29 // Update the longest streak found so far.
30 longestStreak = Math.max(longestStreak, currentStreak);
31 }
32 }
33
34 // Return the longest streak length.
35 return longestStreak;
36 }
37}
38
1#include <vector>
2#include <unordered_set>
3#include <algorithm>
4
5class Solution {
6public:
7 int longestConsecutive(vector<int>& nums) {
8 // Create an unordered set to hold unique elements for constant-time lookups.
9 unordered_set<int> numbersSet(nums.begin(), nums.end());
10 int longestStreak = 0; // Variable to store the length of the longest consecutive sequence found.
11
12 // Iterate over each element in the vector.
13 for (int num : nums) {
14 // Check if the current number is the beginning of a sequence by looking for num - 1.
15 if (!numbersSet.count(num - 1)) {
16 // If num is the start of a sequence, look for all consecutive numbers starting with num + 1.
17 int currentNum = num + 1;
18
19 // Continue checking for the next consecutive number in the sequence.
20 while (numbersSet.count(currentNum)) {
21 currentNum++;
22 }
23
24 // Update the longest streak with the length of the current sequence.
25 longestStreak = max(longestStreak, currentNum - num);
26 }
27 }
28
29 // Return the longest length of consecutive sequence found.
30 return longestStreak;
31 }
32};
33
1// Function to find the length of the longest consecutive elements sequence.
2function longestConsecutive(nums: number[]): number {
3 // Initialising a set to store unique numbers from the input.
4 const numSet: Set<number> = new Set(nums);
5 let longestStreak = 0; // Stores the length of the longest consecutive sequence.
6
7 // Iterate over each number in the set.
8 for (const num of numSet) {
9 // Check if current number is the beginning of a sequence.
10 if (!numSet.has(num - 1)) {
11 let currentNum = num; // Starting number of the current sequence.
12 let currentStreak = 1; // Initializing current streak length.
13
14 // Incrementally check consecutive numbers.
15 while (numSet.has(currentNum + 1)) {
16 currentNum++;
17 currentStreak++;
18 }
19
20 // Update the longest streak if current one is longer.
21 longestStreak = Math.max(longestStreak, currentStreak);
22 }
23 }
24 // Return the length of the longest consecutive sequence.
25 return longestStreak;
26}
27
Time and Space Complexity
The given code is designed to find the length of the longest consecutive elements sequence in an unsorted array. It utilizes a set to achieve an average time complexity of O(n)
.
Time Complexity:
The algorithm has two main parts:
- Creating a set from the list of numbers, which takes
O(n)
time. - Looping through each number in the array and extending the consecutive sequence if the current number is the start of a sequence. This part is also
O(n)
on average because each number is visited only once during the sequence extension process.
Combining these two parts still results in a total of O(n)
time complexity since other operations inside the loop are constant time on average, such as checking for membership in the set and updating the ans
variable.
Space Complexity:
The space complexity is O(n)
because a set is created to store the elements of the array, and no other data structures that depend on the size of the input are used.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!