Longest Consecutive Sequence

12 May 2026 0 Likes

Problem Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

A consecutive sequence consists of numbers that appear continuously in increasing order with a difference of 1 between adjacent elements.

The elements do not need to appear next to each other in the original array.
Example 1:
Input: nums = [100,4,200,1,3,2]
 Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4], so its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
 Output: 9
Explanation: The longest consecutive sequence is [0,1,2,3,4,5,6,7,8], so the length becomes 9.
Example 3:
Input: nums = [1,2,0,1]
 Output: 3
Explanation: The longest consecutive sequence is [0,1,2], so its length is 3.

Constraints

The array may contain positive numbers, negative numbers, and duplicates. The size of the array may vary depending on platform limits.

The output should represent the length of the longest consecutive sequence. An optimal solution is expected to run in linear time complexity.

Understanding the Problem

The problem is asking us to find the length of the largest sequence of numbers that appear consecutively.

A simple way to understand the problem is by first arranging the numbers in sorted order.

For example: nums = [100,4,200,1,3,2]
After sorting: [1,2,3,4,100,200]

Now we can clearly observe that: 1 ā†’ 2 ā†’ 3 ā†’ 4 forms a consecutive sequence because each number differs by exactly 1. Its length becomes: 4

The numbers 100 and 200 do not continue the sequence, so they form smaller sequences individually.

The main challenge is efficiently detecting consecutive sequences without repeatedly sorting or scanning the array unnecessarily.

Hints

The first hint is to think about how quickly we can check whether a number exists in the array. A HashSet provides efficient constant-time lookup operations and can help avoid repeated searches.

Another important observation is that every consecutive sequence has a clear starting point. A number becomes the start of a sequence only if: num - 1 does not exist in the set.

Once the start is identified, we can continue checking: num + 1, num + 2, and so on. This avoids unnecessary repeated processing of the same sequence.

Solutions

BETTER

Sorting Based Consecutive Sequence Solution

This approach first sorts the array so that consecutive numbers appear next to each other.

After sorting, we traverse the array and track the length of the current consecutive sequence.

If nums[i] + 1 == nums[i + 1] then the sequence continues, so we increase the current streak length.

If duplicate elements appear: nums[i] == nums[i + 1], we simply skip them because duplicates do not affect consecutive sequences.

Whenever the sequence breaks, we update the longest streak found so far and start a new sequence.

This approach is much more efficient than repeatedly searching the array because sorting organizes all numbers systematically.
public class B_Sort {

    public int longestConsecutive(int[] nums) {

        if (nums == null || nums.length == 0)
            return 0;

        Arrays.sort(nums);

        int longestStreak = 1;
        int currentStreak = 1;

        for (int i = 0; i < nums.length - 1; i++) {

            if (nums[i] == nums[i + 1]) {
                continue;
            }

            if (nums[i] + 1 == nums[i + 1]) {

                currentStreak++;

            } else {

                longestStreak = Math.max(
                        longestStreak,
                        currentStreak
                );

                currentStreak = 1;
            }
        }

        return Math.max(longestStreak, currentStreak);
    }
}
class Solution:

    def longestConsecutive(self, nums):

        if len(nums) == 0:
            return 0

        nums.sort()

        longest_streak = 1
        current_streak = 1

        for i in range(len(nums) - 1):

            if nums[i] == nums[i + 1]:
                continue

            if nums[i] + 1 == nums[i + 1]:

                current_streak += 1

            else:

                longest_streak = max(
                    longest_streak,
                    current_streak
                )

                current_streak = 1

        return max(longest_streak, current_streak)
Time Complexity
O(n log n)
Space Complexity
O(1)
BRUTE FORCE

Linear Search Based Consecutive Sequence Solution

This approach checks the longest consecutive sequence starting from every element individually.

For each number, we repeatedly search whether the next consecutive number exists in the array.

For example, if the current number is: 1, then we check: 2 exists?, 3 exists?, 4 exists? and continue increasing the sequence length until the next number is no longer found.

To check whether a number exists, we perform a linear search through the array every time.

This process is repeated for every element, making the solution simple to understand but highly inefficient for large input sizes because many repeated searches are performed.
public class A_BruteForce {

    private boolean contains(int[] nums, int target) {

        for (int num : nums) {

            if (num == target)
                return true;

        }

        return false;
    }

    public int longestForThisElement(int element, int[] nums) {

        int count = 1;

        while (contains(nums, element + count)) {
            count++;
        }

        return count;
    }

    public int longestConsecutive(int[] nums) {

        if (nums.length == 0)
            return 0;

        int maxLength = 0;

        for (int num : nums) {

            maxLength = Math.max(
                    maxLength,
                    longestForThisElement(num, nums)
            );
        }

        return maxLength;
    }
}
class Solution:

    def contains(self, nums, target):

        for num in nums:

            if num == target:
                return True

        return False

    def longestForThisElement(self, element, nums):

        count = 1

        while self.contains(nums, element + count):
            count += 1

        return count

    def longestConsecutive(self, nums):

        if len(nums) == 0:
            return 0

        max_length = 0

        for num in nums:

            max_length = max(
                max_length,
                self.longestForThisElement(num, nums)
            )

        return max_length
Time Complexity
O(nĀ²)
Space Complexity
O(1)
OPTIMAL

Optimal HashSet Based Consecutive Sequence Solution

This approach uses a HashSet to efficiently detect consecutive sequences using constant-time lookup operations.

First, all numbers are inserted into the set so that existence checks become very fast.

The key observation is that a number can start a new consecutive sequence only if: num - 1 does not exist in the set.

For example: If 1 exists but 0 does not exist, then 1 becomes the starting point of a sequence.

From that starting point, we continuously check: num + 1, num + 2, and so on, until the sequence breaks. During this process, we calculate the current streak length and update the longest sequence found so far.

This approach avoids unnecessary repeated processing because each sequence is traversed only once.
public class C_Hash {

    public int longestConsecutive(int[] nums) {

        if (nums == null || nums.length == 0)
            return 0;

        Set<Integer> set = new HashSet<>(nums.length);

        for (int num : nums) {
            set.add(num);
        }

        int longestStreak = 0;

        for (int num : set) {

            if (!set.contains(num - 1)) {

                int currentNum = num;

                int currentStreak = 1;

                while (set.contains(currentNum + 1)) {

                    currentNum++;

                    currentStreak++;
                }

                longestStreak = Math.max(
                        longestStreak,
                        currentStreak
                );
            }
        }

        return longestStreak;
    }
}
class Solution:

    def longestConsecutive(self, nums):

        if len(nums) == 0:
            return 0

        num_set = set(nums)

        longest_streak = 0

        for num in num_set:

            if (num - 1) not in num_set:

                current_num = num
                current_streak = 1

                while (current_num + 1) in num_set:

                    current_num += 1
                    current_streak += 1

                longest_streak = max(
                    longest_streak,
                    current_streak
                )

        return longest_streak
Time Complexity
O(n)
Space Complexity
O(n)

Conclusion

The Longest Consecutive Sequence problem is an important interview problem that teaches efficient sequence detection using hash-based lookup techniques.

The problem demonstrates how proper use of a HashSet can drastically improve performance by avoiding unnecessary repeated searches and sorting operations.

Mastering this problem helps build a strong understanding of sets, sequence processing, and efficient traversal strategies, which are commonly used in coding interviews and real-world systems.

šŸ’¬ Comments