Given an unsorted integer array nums, possibly containing duplicate values. Consecutive values do not need to occupy adjacent positions in the array. Find the length of the longest sequence of distinct consecutive integers.
Example 1
Input: nums = [100, 4, 200, 1, 3, 2, 2, 5]
Output: 5
Explanation: The values 1, 2, 3, 4, 5 form the longest consecutive sequence. The duplicate 2 does not increase its length.
Example 2
Input: nums = [0, -1, 1, 2, -2, 4]
Output: 5
Explanation: The longest sequence is -2, -1, 0, 1, 2, so its length is 5.
Brute Force Approach
Treat each distinct array value as a possible sequence beginning. A value can begin a maximal sequence only when its predecessor is absent. From every valid beginning, search the array repeatedly for the next consecutive value.
Duplicate candidates are skipped before expansion. This prevents the same sequence from being rebuilt merely because its first value occurs more than once. The method uses no auxiliary data structure, but repeated full-array searches make it quadratic.
Algorithm
Initialize the longest length to
0; this already gives the correct result when the array is empty.Visit every candidate position, scan earlier positions, and skip the candidate when the same value has already been processed.
Search the complete array for the candidate's predecessor and continue only when that predecessor is absent.
Start the sequence length at
1, then repeatedly rescan the array for the next consecutive value.Stop expanding when the required next value is absent, and update the longest length with the completed sequence.
After every candidate position has been considered, return the longest length.
Dry Run
brute force
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Returns true when the target value occurs in the array. bool linearSearch(vector<int>& nums, int target) { // Inspect every array position for the requested value. for (int scanIndex = 0; scanIndex < nums.size(); scanIndex++) { // A match confirms that the target is present. if (nums[scanIndex] == target) { return true; } } return false; }public: // Returns the length of the longest consecutive sequence. int longestConsecutive(vector<int>& nums) { int n = nums.size(); int longestLength = 0; // Use every array element as the beginning of a possible sequence. for (int startIndex = 0; startIndex < n; startIndex++) { int currentLength = 1; int nextValue = nums[startIndex] + 1; // Extend the sequence while the next integer exists in the array. while (linearSearch(nums, nextValue)) { currentLength++; nextValue++; } longestLength = max(longestLength, currentLength); } return longestLength; }};// Driver codeint main() { vector<int> nums = {100, 4, 200, 1, 3, 2, 2, 5}; // instance for class Solution Solution sol; cout << sol.longestConsecutive(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n³) in the worst case. There are n starting elements, one starting element may extend through O(n) consecutive values, and every linear search examines up to n array positions.
Space Complexity: O(1) auxiliary space. Only counters, values, and Boolean flags are stored.
Better Approach
Instead of repeatedly searching the unsorted array, sorting places equal values together and arranges consecutive values next to each other. One left-to-right scan can then ignore duplicates, extend a sequence when adjacent distinct values differ by one, and restart after a larger gap.
A sorted copy is used so the original input remains unchanged. This removes the repeated searches but introduces sorting time and storage for the copy.
Algorithm
If the array is empty, return
0; otherwise, create a copy and sort it in ascending order.Initialize both the current sequence length and the longest length to
1, using the first sorted value as the previous distinct value.Scan the sorted copy from its second position to the end.
Ignore a value equal to the previous distinct value, extend the sequence when it is exactly one greater, and reset the current length after a larger gap.
After each new distinct value, update the previous value and the longest recorded length.
Return the longest length after the sorted scan terminates.
Dry Run
better
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the length of the longest consecutive sequence. int longestConsecutive(vector<int>& nums) { vector<int> sortedNums = nums; // An empty array contains no sequence. if (sortedNums.empty()) { return 0; } // Sorting a copy preserves the original input. sort(sortedNums.begin(), sortedNums.end()); int currentLength = 1; int longestLength = 1; int previousValue = sortedNums[0]; // Compare each sorted value with the previous distinct value. for (int index = 1; index < sortedNums.size(); index++) { // A duplicate must not change the current sequence length. if (sortedNums[index] == previousValue) { continue; } // A value exactly one greater extends the current sequence. else if (sortedNums[index] == previousValue + 1) { currentLength++; } // Any larger gap starts a new sequence at the current value. else { currentLength = 1; } previousValue = sortedNums[index]; longestLength = max(longestLength, currentLength); } return longestLength; }};// Driver codeint main() { vector<int> nums = {100, 4, 200, 1, 3, 2, 2, 5}; // instance for class Solution Solution sol; cout << sol.longestConsecutive(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n log n). Creating the copy takes O(n), sorting takes O(n log n), and the final scan takes O(n).
Space Complexity: O(n) auxiliary space for the sorted copy. The sorting routine may also use implementation-dependent stack or temporary storage.
Optimal Approach
Sorting establishes more order than the answer needs. A hash set provides direct membership checks while also removing duplicates, so the input does not need to be rearranged.
Only a value whose predecessor is absent can begin a sequence. Once such a beginning is found, successive values are checked until the first gap appears. Every distinct value is expanded as part of only one sequence, which gives expected linear time.
Algorithm
Insert every array value into a hash set so duplicates are removed and membership can be checked directly.
Initialize the longest length to
0; an empty set therefore returns0without special handling.Examine each distinct value and skip it when its predecessor exists, because it lies inside an earlier sequence.
For a value without a predecessor, start a new sequence with length
1.Check successive values in the set, increasing the current length until the first missing successor ends the sequence.
Update the longest length after each completed sequence and return it after all distinct values have been examined.
Dry Run
Optimal Approach
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the length of the longest consecutive sequence. int longestConsecutive(vector<int>& nums) { unordered_set<int> values(nums.begin(), nums.end()); int longestLength = 0; // Examine every distinct value as a possible sequence start. for (int value : values) { // A present predecessor means this value lies inside a sequence. if (values.count(value - 1)) { continue; } int currentLength = 1; int nextValue = value + 1; // Extend the sequence while each next consecutive value exists. while (values.count(nextValue)) { currentLength++; nextValue++; } longestLength = max(longestLength, currentLength); } return longestLength; }};// Driver codeint main() { vector<int> nums = {100, 4, 200, 1, 3, 2, 2, 5}; // instance for class Solution Solution sol; cout << sol.longestConsecutive(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n) expected time. Building the set takes expected O(n), and each distinct value is examined once and expanded only from its sequence beginning. Pathological hash collisions can degrade the worst case.
Space Complexity: O(n) auxiliary space for the hash set of distinct values.
Interview follow-up Questions
A value with an existing predecessor lies inside a sequence, so expanding from it would repeat work already covered by the true beginning. A missing predecessor proves that the value is the smallest member of its maximal consecutive sequence. The brute-force approach deliberately does not apply this optimization.
Be the first to add a comment.