Author at SyntaxFlow
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
A consecutive sequence means the numbers in the sequence must be consecutive integers (e.g., [1, 2, 3, 4]), meaning each number is exactly 1 greater than the previous one.
The catch? The elements do not need to be next to each other in the original array, and you must design an algorithm that runs in O(n) time complexity.
nums = [100, 4, 200, 1, 3, 2]4[1, 2, 3, 4]. Its length is 4. Notice that even though these numbers are scattered across the array, they form a perfect continuous chain when reordered conceptually.nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]9[0, 1, 2, 3, 4, 5, 6, 7, 8]. Its length is 9. (Note: Duplicate elements like the extra 0 do not extend the sequence length).Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109When encountering this problem for the first time, the most instinctive way to solve it is to explore every possible continuous chain from scratch. Since the array is completely unsorted, we pick each number one by one and check if it can serve as the starting point of our longest consecutive sequence.
Imagine you have a deck of cards scattered randomly on a table. To find the longest consecutive run of numbers without sorting them, you might pick up a card—say, a 4—and then scan the entire table looking for a 5. If you find it, you look for a 6, then a 7, and so on, until a number is missing. You write down how long that chain was. Then, you put those cards back, pick the next card from the table, and repeat the entire process.
By running a linear search across the entire array for the "next" consecutive number over and over again, we can track the maximum streak length found.
To turn this intuition into a formal algorithm, we rely on a helper function to perform linear searches alongside our main tracking loop:
arrayContains(arr, target) that loops through the array to check if a specific target number exists.longest_streak = 0. If the input array is empty, return 0.num in the nums array:current_num = num.current_streak = 1.arrayContains(nums, current_num + 1) returns true.current_num by 1 and increment current_streak by 1.longest_streak if the current chain is longer: longest_streak = max(longest_streak, current_streak).longest_streak once all numbers have been checked.Array: [3, 1, 4, 2]
🔄 Loop i=0: num = 3
├── Check 4? 🟢 YES ➡️ [3, 4] (Streak: 2)
└── Check 5? 🔴 NO
📊 Max Streak = 2
🔄 Loop i=1: num = 1
├── Check 2? 🟢 YES ➡️ [1, 2]
├── Check 3? 🟢 YES ➡️ [1, 2, 3]
├── Check 4? 🟢 YES ➡️ [1, 2, 3, 4] (Streak: 4)
└── Check 5? 🔴 NO
📊 Max Streak = 4 🔥 (Updated)
🔄 Loop i=2: num = 4
└── Check 5? 🔴 NO ➡️ [4] (Streak: 1)
📊 Max Streak = 4
🔄 Loop i=3: num = 2
├── Check 3? 🟢 YES ➡️ [2, 3]
├── Check 4? 🟢 YES ➡️ [2, 3, 4] (Streak: 3)
└── Check 5? 🔴 NO
📊 Max Streak = 4
🏁 FINAL ANSWER: 4class Solution {
private:
// Helper function to do a simple linear search
bool arrayContains(vector<int>& arr, int target) {
for (int x : arr) {
if (x == target) {
return true;
}
}
return false;
}
public:
int longestConsecutive(vector<int>& nums) {
// Edge case: if array is empty, the longest sequence is 0
if (nums.empty()) {
return 0;
}
int longest_streak = 0;
// Pick each number one by one
for (int num : nums) {
int current_num = num;
int current_streak = 1;
// Check if the next consecutive number exists in the array
while (arrayContains(nums, current_num + 1)) {
current_num += 1;
current_streak += 1;
}
// Keep track of the maximum streak we have seen so far
longest_streak = max(longest_streak, current_streak);
}
return longest_streak;
}
};While this solution is highly intuitive, its performance makes it completely unusable for larger datasets.
for loop that runs n times to inspect each number.while loop that, in the worst case (e.g., a perfectly consecutive array like [1, 2, 3, 4, 5]), can also run up to n times.longest_streak, current_streak), requiring no extra memory layout.Article Note: Passing this brute-force solution on platforms like LeetCode will instantly result in a TLE (Time Limit Exceeded) error. It serves as the perfect stepping stone to explain why we need to optimize our search time using smarter strategies.
If the main issue with the brute force method is that elements are scattered all over the place, the most logical first optimization is to bring order to the chaos. By sorting the array, elements that belong in a consecutive sequence will be forced to sit right next to each other.
Let's take our original unsorted array: [100, 4, 200, 1, 3, 2]
If we sort this array in ascending order, it becomes: [1, 2, 3, 4, 100, 200]
Now, instead of scanning the entire array over and over again to find the next number, we can just walk through the sorted array a single time (a linear scan). We check if the current element is exactly 1 greater than the previous element. If it is, we extend our streak!
Before writing the code, there is a massive edge case your readers need to know about: Duplicates.
Consider an array like [1, 2, 2, 3, 4]. When we are at index 1 (2) and look at index 2 (2), the difference is 0. The streak hasn't broken, but it also hasn't grown. If our code isn't careful, seeing a duplicate might falsely reset our streak counter.
The Fix: When we encounter two identical adjacent numbers, we simply skip the element and move on without incrementing or resetting our streak.
0.longest_streak = 1 and current_streak = 1.previous_element + 1, increment current_streak by 1.previous_element, do nothing and skip to the next iteration.longest_streak = max(longest_streak, current_streak) and reset current_streak = 1.5. Return max(longest_streak, current_streak) to catch any streaks running to the very end of the array.
Dry Run
Sorted Array: [1, 2, 2, 3, 4, 100]
Initial State:
├── longest_streak = 1
└── current_streak = 1
🔄 i = 1 (Value: 2 | Previous: 1)
├── Condition: Consecutive element! (2 == 1 + 1)
├── Action: current_streak++ ➡️ 2
└── Status: Streak is growing
🔄 i = 2 (Value: 2 | Previous: 2)
├── Condition: Duplicate element! (2 == 2)
├── Action: Do nothing, skip to next index
└── Status: Streak is paused
🔄 i = 3 (Value: 3 | Previous: 2)
├── Condition: Consecutive element! (3 == 2 + 1)
├── Action: current_streak++ ➡️ 3
└── Status: Streak is growing
🔄 i = 4 (Value: 4 | Previous: 3)
├── Condition: Consecutive element! (4 == 3 + 1)
├── Action: current_streak++ ➡️ 4
└── Status: Streak is growing
🔄 i = 5 (Value: 100 | Previous: 4)
├── Condition: Chain is broken! (100 != 4 + 1)
├── Action:
│ ├── longest_streak = max(1, 4) ➡️ 4 🔥 (Updated)
│ └── current_streak resets to 1
└── Status: Streak is dead
🏁 Final Check: max(longest_streak, current_streak) ➡️ max(4, 1)
🏁 FINAL ANSWER: 4C++ code
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
// Edge case: if array is empty, return 0
if (nums.empty()) {
return 0;
}
// Sort the array first
sort(nums.begin(), nums.end());
int longest_streak = 1;
int current_streak = 1;
// Linear scan through the sorted array
for (int i = 1; i < nums.size(); i++) {
// Skip duplicates
if (nums[i] != nums[i - 1]) {
// If consecutive, increase current streak
if (nums[i] == nums[i - 1] + 1) {
current_streak++;
}
// If chain breaks, save the max and reset current streak
else {
longest_streak = max(longest_streak, current_streak);
current_streak = 1;
}
}
}
// One final check to capture the last running streak
return max(longest_streak, current_streak);
}
};std::sort, it sorts the array in-place, meaning we don't allocate any extra tracking arrays or data structures.While sorting got us closer to the finish line, we are still tied down by that O(nlog n) sorting bottleneck. To achieve a true, lightning-fast O(n) runtime, we need a way to look up elements instantly without changing their positions. Enter: The Hash Set approach.
This is the climax of your article! This is where you show your readers how to completely shatter that bottleneck and achieve a blazing-fast, interview-ready time complexity using a Hash Set.
To completely eliminate sorting, we need a way to look up if a number exists instantly. A Hash Set gives us exactly that: average time complexity for lookups.
But if we just put everything in a set and search for the next numbers blindly, we run into the same problem as the brute force method—redundant work. We need a way to only start counting a sequence when we are standing at the absolute beginning of it.
Imagine a sequence of consecutive numbers scattered in your array: [1, 2, 3, 4].
If we check for a streak starting at 2, 3, or 4, we are doing useless, repetitive calculations. We only want to kick off our counting loop when we are standing at 1—the Chain Leader.
How do we identify a Chain Leader?
A number num is the absolute start of a sequence if num - 1 does not exist in the array.
3 a leader? Check 3 - 1 = 2. 2 exists, so No.1 a leader? Check 1 - 1 = 0. 0 does not exist in our array, so Yes!By using this simple check, we ensure that we only enter our counting while loop for the start of each sequence. Every element inside a sequence will be visited exactly once by the counting loop, keeping our runtime beautifully linear.
unordered_set. This automatically removes duplicates and sets up lookups.longest_streak = 0.num in your set:num - 1.num - 1 is not found, it means num is a sequence starter!current_num = num and current_streak = 1.while loop: as long as current_num + 1 exists in the set, keep incrementing current_num and current_streak.longest_streak = max(longest_streak, current_streak).longest_streak.Let's trace how efficiently this runs using the array: nums = [100, 4, 200, 1, 3, 2]
{100, 4, 200, 1, 3, 2}longest_streak = 0Set Elements: {100, 4, 200, 1, 3, 2}
🔄 Checking num = 100
├── Is (100 - 1 = 99) in set? 🔴 NO ➡️ 👑 100 is a Chain Leader!
├── Counting loop: Is 101 in set? 🔴 NO
└── Max updated: max(0, 1) ➡️ 1
🔄 Checking num = 4
├── Is (4 - 1 = 3) in set? 🟢 YES ➡️ Not a leader. Skip!
🔄 Checking num = 200
├── Is (200 - 1 = 199) in set? 🔴 NO ➡️ 👑 200 is a Chain Leader!
├── Counting loop: Is 201 in set? 🔴 NO
└── Max stays: max(1, 1) ➡️ 1
🔄 Checking num = 1
├── Is (1 - 1 = 0) in set? 🔴 NO ➡️ 👑 1 is a Chain Leader!
├── Counting loop:
│ ├── Is 2 in set? 🟢 YES ➡️ Streak: 2
│ ├── Is 3 in set? 🟢 YES ➡️ Streak: 3
│ └── Is 4 in set? 🟢 YES ➡️ Streak: 4
│ └── Is 5 in set? 🔴 NO ➡️ Chain ends.
└── Max updated: max(1, 4) ➡️ 4 🔥
🔄 Checking num = 3
├── Is (3 - 1 = 2) in set? 🟢 YES ➡️ Not a leader. Skip!
🔄 Checking num = 2
├── Is (2 - 1 = 1) in set? 🟢 YES ➡️ Not a leader. Skip!
🏁 FINAL ANSWER: 4c++ code
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
// Create a Hash Set and dump all elements into it
unordered_set<int> num_set(nums.begin(), nums.end());
int longest_streak = 0;
// Traverse the elements of the set
for (int num : num_set) {
// Check if 'num' is the absolute start of a sequence
if (num_set.find(num - 1) == num_set.end()) {
int current_num = num;
int current_streak = 1;
// Push forward to find the rest of the chain
while (num_set.find(current_num + 1) != num_set.end()) {
current_num += 1;
current_streak += 1;
}
// Track the maximum continuous chain found
longest_streak = max(longest_streak, current_streak);
}
}
return longest_streak;
}
};while loop only triggers if a number is a sequence leader. An element that belongs to a chain is only looked up and iterated through exactly once during the entire runtime inside that while loop. This means each number is touched at most twice overall, yielding a true linear time complexity of .unordered_set that stores up to n elements from the original array to achieve fast O(1) lookups.Video Reference:
https://youtu.be/oO5uLE7EUlM?si=SyxkvMC3Zw6wqw_4
Problem try out: