grid47 Exploring patterns and algorithms
Oct 25, 2024
5 min read
Solution to LeetCode 128: Longest Consecutive Sequence Problem
Given an unsorted array of integers, return the length of the longest consecutive elements sequence.
Problem
Approach
Steps
Complexity
Input: The input is an unsorted array of integers.
Example: [1, 2, 4, 5, 6, 3]
Constraints:
• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
Output: The output should be the length of the longest consecutive sequence in the array.
Example: 6
Constraints:
• The output will be an integer representing the length of the longest consecutive sequence.
Goal: To find the longest consecutive sequence, we need to track elements and determine the sequence length efficiently.
Steps:
• 1. Insert all elements into a set for constant time lookup.
• 2. For each element, check if it is the start of a new sequence by checking if the previous element (element - 1) is not in the set.
• 3. If it is the start of a sequence, continue checking for consecutive elements by incrementing the current element and counting the sequence length.
• 4. Track the maximum sequence length found.
Goal: The input array will always be valid as per the given constraints.
Steps:
• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
Assumptions:
• The input array may contain duplicate values which should not affect the length of the longest sequence.
• Input: [1, 2, 4, 5, 6, 3]
• Explanation: The sequence [1, 2, 3, 4, 5, 6] is the longest consecutive sequence in this array, having length 6.
• Input: [10, 100, 5, 11, 6, 7]
• Explanation: The longest consecutive sequence is [5, 6, 7, 10, 11] with length 5.
Approach: Use a set to store the elements for quick lookup and determine the longest consecutive sequence in linear time.
Observations:
• The problem asks for the longest consecutive sequence in an unsorted array.
• Using a set allows us to look up elements in constant time, making the solution more efficient.
• The solution involves inserting all elements into a set, then iterating through them and checking for consecutive sequences.
Steps:
• 1. Insert all elements from the input array into a set for O(1) lookup.
• 2. For each element, check if it is the beginning of a new consecutive sequence.
• 3. If it is, count the length of the consecutive sequence.
• 4. Keep track of the maximum sequence length found during the iteration.
Empty Inputs:
• If the input array is empty, the longest consecutive sequence length is 0.
Large Inputs:
• The solution should handle inputs with up to 10^5 elements efficiently.
Special Values:
• If the input contains duplicates, they should be ignored since they do not affect the sequence length.
Constraints:
• The input array will contain between 0 and 10^5 elements, and the range of values will be between -10^9 and 10^9.
intlongestConsecutive(vector<int>& nums) {
set<int> s;
for(intx: nums)
s.insert(x);
if(s.empty()) return0;
int mx =1;
for(int i =0; i < nums.size(); i++) {
int y = nums[i];
int c =1;
if(!s.count(y +1))
while(s.count(y -1)) {
c++;
y = y -1;
mx = max(mx, c);
}
}
return mx;
}
1 : Function Declaration
intlongestConsecutive(vector<int>& nums) {
Define the function `longestConsecutive` that takes a vector of integers `nums` as input.
2 : Set Initialization
set<int> s;
Initialize an empty set `s` to store unique numbers from the input vector `nums`.
3 : Loop Iteration
for(intx: nums)
Iterate through each element `x` in the input vector `nums`.
4 : Set Insertion
s.insert(x);
Insert the current element `x` into the set `s`. This ensures all elements are unique.
5 : Empty Check
if(s.empty()) return0;
Check if the set is empty. If it is, return 0 as there are no elements to form a consecutive sequence.
6 : Variable Initialization
int mx =1;
Initialize the variable `mx` to 1 to keep track of the longest consecutive sequence found.
7 : Loop Iteration
for(int i =0; i < nums.size(); i++) {
Iterate through each element of the `nums` vector again to find consecutive sequences.
8 : Element Assignment
int y = nums[i];
Assign the current element `nums[i]` to the variable `y` for checking its consecutive sequence.
9 : Sequence Length Initialization
int c =1;
Initialize the counter `c` to 1 to count the current length of the consecutive sequence.
10 : Existence Check
if(!s.count(y +1))
Check if the next consecutive number `y + 1` does not exist in the set. If not, attempt to find the previous consecutive numbers.
11 : Loop for Consecutive Elements
while(s.count(y -1)) {
Enter a while loop to check if the previous consecutive number `y - 1` exists in the set.
12 : Counter Update
c++;
Increment the counter `c` for each consecutive element found.
13 : Pointer Update
y = y -1;
Update `y` to the previous consecutive element `y - 1`.
14 : Maximum Length Update
mx = max(mx, c);
Update `mx` to the maximum length of consecutive sequence found so far.
15 : Return Statement
return mx;
Return the maximum length of the longest consecutive sequence found.
Best Case: O(n), where n is the length of the array.
Average Case: O(n), since we iterate through the array and each element is inserted and looked up in the set in constant time.
Worst Case: O(n), as we always process each element once.
Description: The time complexity is O(n) because we only process each element once and look up elements in constant time using the set.
Best Case: O(n), as we need a set to store the elements.
Worst Case: O(n), since we store all elements in a set.
Description: The space complexity is O(n), as we use a set to store the elements of the array.
