Longest Consecutive Sequence LeetCode 128 Explained

The Problem Statement

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.

Understanding with Examples

Example 1

• Input: nums = [100, 4, 200, 1, 3, 2]
• Output: 4
• Explanation: The longest consecutive elements sequence is [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.

Example 2

• Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
• Output: 9
• Explanation: The longest consecutive elements sequence is [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] <= 109

The Brute Force Approach

When 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.

1. Intuition

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.

2. The Algorithm

To turn this intuition into a formal algorithm, we rely on a helper function to perform linear searches alongside our main tracking loop:

1. Create a helper function arrayContains(arr, target) that loops through the array to check if a specific target number exists.
2. In the main function, initialize a variable longest_streak = 0. If the input array is empty, return 0.
3. Loop through every element num in the nums array:
   • Set a temporary tracker current_num = num.
   • Set a temporary streak counter current_streak = 1.
   • Open a while loop that continues running as long as arrayContains(nums, current_num + 1) returns true.
   • Inside this while loop, increment current_num by 1 and increment current_streak by 1.
4. After exiting the while loop for the current element, update longest_streak if the current chain is longer: longest_streak = max(longest_streak, current_streak).
5. Return longest_streak once all numbers have been checked.

3. Detailed Dry Run

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: 4

C++ code

class 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;
    }
};

5. Complexity Analysis

While this solution is highly intuitive, its performance makes it completely unusable for larger datasets.

• Time Complexity: O(n³) (Cubic Time)
  • We have an outer for loop that runs n times to inspect each number.
  • Inside, we have a 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.
  • Finally, inside that while loop, our helper function performs a linear scan across the array to find the next number, which takes O(n) time.
  • Multiplying these three nested layers together ($n \times n \times n$) yields a massive worst-case time complexity of O(n³). If an interviewer gives you an array of just 1,000 elements, this approach could require up to a billion operations!
• Space Complexity: O(1) (Constant Space)
  • The only advantage of this method is that it is highly memory-efficient. We are modifying nothing and only tracking the counts using basic integer variables (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.

The Better Approach: Sorting

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.

1. Intuition

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!

2. Handling the Duplicate Trap

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.

3. The Algorithm

1. Check if the array is empty. If it is, return 0.
2. Sort the array in ascending order.
3. Initialize two variables: longest_streak = 1 and current_streak = 1.
4. Loop through the sorted array starting from the second element (index 1):
   • Case A (Consecutive): If the current element is exactly equal to previous_element + 1, increment current_streak by 1.
   • Case B (Duplicate): If the current element is equal to previous_element, do nothing and skip to the next iteration.
   • Case C (Broken Chain): If the chain breaks, update 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: 4

C++ 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);
    }
};

6. Complexity Analysis

• Time Complexity: O(n log n)
  • The most expensive operation here is sorting the array, which takes $O(n \log n)$ time. The subsequent linear scan only takes $O(n)$ time. Therefore, the overall runtime is dominated by the sort step: O(n log n).
• Space Complexity: O(1)
  • Since we are using C++'s 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 $O(n \log n)$ bottleneck and achieve a blazing-fast, interview-ready $O(n)$ time complexity using a Hash Set.

The Optimal Approach: The Hash Set "Chain Leader" Trick

To completely eliminate sorting, we need a way to look up if a number exists instantly. A Hash Set gives us exactly that: $O(1)$ 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.

1. Core Intuition: Finding the "Chain Leader"

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.

• Is 3 a leader? Check 3 - 1 = 2. 2 exists, so No.
• Is 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.

2. The Optimal Algorithm

1. Insert all elements from the array into an unordered_set. This automatically removes duplicates and sets up $O(1)$ lookups.
2. Initialize longest_streak = 0.
3. Loop through each unique num in your set:
   • Check if it's a Chain Leader: Search the set for num - 1.
   • If num - 1 is not found, it means num is a sequence starter!
   • Initialize current_num = num and current_streak = 1.
   • Open a while loop: as long as current_num + 1 exists in the set, keep incrementing current_num and current_streak.
   • Update longest_streak = max(longest_streak, current_streak).
4. Return longest_streak.

3. Step-by-Step Dry Run

Let's trace how efficiently this runs using the array: nums = [100, 4, 200, 1, 3, 2]

• Hash Set created: {100, 4, 200, 1, 3, 2}
• Initial State: longest_streak = 0

Set 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: 4

c++ 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;
    }
};

Complexity Analysis

• Time Complexity: $O(n)$ (Linear Time)
  • Wait, isn't there a while loop inside a for loop? Yes, it looks like O(n^2) on the surface, but it's not! The 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 $O(n)$.
• Space Complexity: O(n)(Linear Space)
  • We traded a little bit of memory to gain that massive speed boost. We allocate an 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:

Longest Consecutive Sequence - LeetCode