Longest Consecutive Sequence | Leetcode 128

Struggling with the “Longest Consecutive Sequence” problem on LeetCode? This blog will help you understand the problem, walk you through three different solutions (Brute Force, Better, and Optimal), and explain every step. Let’s get started!

Here’s the [Problem Link] to begin with.

What Does the Problem Say?

You are given an unsorted array of integers. Your task is to find the length of the longest sequence of consecutive numbers (numbers that come one after another, like 1, 2, 3, 4) in the array. The sequence elements can be in any order in the input array.

Example 1

Input:
arr = [100, 4, 200, 1, 3, 2 ]

Explanation:
The longest consecutive sequence is `[1, 2, 3, 4] the answer is 4.

Example 2

Input:
arr = [0, 3, 7, 2, 5, 8, 4, 6, 0]

Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, is 9.

Brute Force Solution

Intuition and Approach

Let’s break down the simplest way to solve this problem:

1. Pick Each Number:
   For every number in the array, try to build the longest consecutive sequence starting from that number.
2. Count Consecutive Numbers:
   For each starting number, keep checking if the next number (num + 1) exists in the array. If yes, increase your count and check for the next number.
3. Track the Maximum:
   Keep track of the largest count you find for any starting number. This will be your answer.

Why does this work?
We are trying every possible starting point and counting how far we can go consecutively. It’s simple but can be slow for large arrays because we keep searching the array for each next number.

Code Implementation

def longestSuccessiveElements(arr: List[int]) -> int:
    max_count = 0
    n = len(arr)
    for i in range(0, n):
        num = arr[i]
        count = 1
        # Check for the next consecutive numbers
        while num + 1 in arr:
            count += 1
            num += 1
        max_count = max(max_count, count)
    return max_count

Code Explanation

• We loop through each element of the array.
• For each element, we try to find the next consecutive number (num + 1) in the array.
• We keep increasing the count as long as we find the next number.
• We update the maximum count whenever we find a longer sequence.

Dry Run

Input:
arr = [100, 4, 200, with 100`:

• Sequence is just “ (count = 1)
• Start with 4: Sequence is just “ (count = 1)
• Start with 200: Sequence is just “ (count = 1)
• Start with 1: Sequence is `[1, 2, 3,nt = 4)
• Start with 3: Sequence is just `[3,count = 2)
• Start with 2: Sequence is “ (count = 3)

Maximum count found is 4.

Time and Space Complexity

• Time Complexity: O(N^2)
  For each element, we may search the whole array to find consecutive numbers.
• Space Complexity: O(1)
  No extra space is used except for a few variables.

Conclusion

The brute force approach is easy to understand but not efficient for large arrays. It will work for small inputs or for understanding the problem.

Better Solution

Intuition and Approach

Let’s try to make the solution faster:

1. Sort the Array:
   If the array is sorted, consecutive numbers will be next to each other. This makes it easy to count sequences.
2. Count Consecutive Runs:
   Go through the sorted array. For each number, if it is exactly one more than the previous number, increase the count. If it’s a duplicate, skip it. If it’s not consecutive, reset the count to 1.
3. Track the Longest:
   Keep updating the longest sequence found.

Why does this work?
Sorting brings all consecutive numbers together, so we can count them in a single pass.

Code Implementation

from typing import List

def longestSuccessiveElements(arr: List[int]) -> int:
    arr.sort()  # Sort the array so consecutive numbers are next to each other
    last_smaller = float("-inf")  # To keep track of the previous number
    count = 0  # Current consecutive sequence length
    longest = 0  # Longest sequence found

    for num in arr:
        if num - 1 == last_smaller:  # Check if current is consecutive
            count += 1
            last_smaller = num
        elif num != last_smaller:  # Skip duplicates
            count = 1
            last_smaller = num
        longest = max(longest, count)  # Update the answer

    return longest

Code Explanation

• We sort the array first.
• We use last_smaller to keep track of the last unique number.
• If the current number is consecutive to the last, we increase the count.
• If it’s a duplicate, we skip.
• If it’s not consecutive, we reset the count.
• We keep updating the longest sequence found.

Dry Run

Input:
arr = [100, 4, 200, sorting: [1, 2, 3, 4, 100, start new sequence (count = 1)

• 2 → consecutive (count = 2)
• 3 → consecutive (count = 3)
• 4 → consecutive (count = 4)
• 100 → not consecutive, reset (count = 1)
• 200 → not consecutive, reset (count = 1)

Maximum count found is 4.

Time and Space Complexity

• Time Complexity: O(N log N)
  Because of sorting.
• Space Complexity: O(1)
  No extra space except for a few variables.

Conclusion

The better solution is much faster than brute force for large arrays. It uses sorting to make counting consecutive numbers easy.

Optimal Solution

Intuition and Approach

Can we solve this problem even faster, without sorting? Yes! Here’s how:

1. Use a Set:
   Store all numbers in a set. This allows us to check if a number exists in O(1) time.
2. Find Sequence Starts:
   For each number, check if it could be the start of a sequence (i.e., num - 1 is not in the set).
3. Count the Sequence:
   For each start, count how many consecutive numbers exist by checking num + 1, num + 2, etc.
4. Update the Longest:
   Keep updating the longest sequence found.

Why does this work?
We only start counting from the beginning of a sequence, so we never count the same sequence twice. Using a set makes lookups fast.

Code Implementation

from typing import List

def longestSuccessiveElements(arr: List[int]) -> int:
    my_set = set()
    # Populate the set with all elements from arr
    for num in arr:
        my_set.add(num)

    longest = 0

    # For each number, check if it can start a new sequence
    for num in my_set:
        if num - 1 not in my_set:  # indicates a sequence start
            x = num
            count = 1

            # Expand the sequence as far as possible
            while x + 1 in my_set:
                count += 1
                x += 1

            # Track the longest run
            longest = max(longest, count)

    return longest

Code Explanation

• We store all numbers in a set for fast lookups.
• For each number, if num - 1 is not in the set, it means this number could be the start of a sequence.
• We keep checking for num + 1, num + 2, etc., and count how long the sequence is.
• We update the longest sequence found.

Dry Run

Input:
arr = [100, 4, 200,: {1, 2, 3, 4, 100, 200}`

• For 1: 0 not in set, so start sequence.
  • 2 in set → count = 2
  • 3 in set → count = 3
  • 4 in set → count = 4
  • 5 not in set → stop
• For 2: 1 in set → skip
• For 3: 2 in set → skip
• For 4: 3 in set → skip
• For 100: 99 not in set → start sequence. Only 100 present (count = 1)
• For 200: 199 not in set → start sequence. Only 200 present (count = 1)

Maximum count found is 4.

Time and Space Complexity

• Time Complexity: O(N)
  Each number is processed at most twice (once as a possible start, and once in the while loop).
• Space Complexity: O(N)
  We use a set to store all numbers.

Conclusion

The optimal solution is the best for this problem. It uses a set to find sequences quickly and avoids unnecessary work. This is the approach you should use in interviews or for large inputs.

Final Thoughts

The “Longest Consecutive Sequence” problem is a great example of how to improve your solution step by step. Start with brute force to understand the problem, then use sorting for a better solution, and finally use a set for the most efficient answer.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.