Longest Consecutive Sequence in an Array

Given an array nums of n integers.

Return the length of the longest sequence of consecutive integers. The integers in this sequence can appear in any order.

Note: Can have repeating numbers

Brute Force#

For every element x in the array, check whether x+1, x+2, ... exist using a linear scan each time. The triple nesting (outer loop for each element, inner loop for each consecutive candidate, innermost scan to verify presence) gives O(n³) time — far too slow for large inputs.

• For every element, use linear search to find consecutive numbers
• 3 loops
  • for each element
  • to check consecutive element
  • for linear search
• TC: O(n^3) --> TLE

Better Approach#

Sorting brings consecutive numbers adjacent to each other, reducing membership checks from O(n) to O(1) comparisons. We walk through the sorted array maintaining lastSmaller to skip duplicates and len to count the current streak. When an element breaks the streak (nums[i] != lastSmaller + 1 and is not a duplicate), we reset. This costs O(n log n) for sorting, which is a major improvement over O(n³) but still slower than the hash-set approach.

• Sort the array and find consecutive
• Keep a note of lastSmaller, as repetition can be there

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        // use lastSmaller as same number can repeat
        int len = 1, maxLen = -1, lastSmaller=INT_MIN;
        for(int i=0;i<nums.size();i++){
            if(nums[i] - 1 == lastSmaller){
                len++;
                lastSmaller = nums[i];
            }
            else if(nums[i] != lastSmaller){
                len=1;
                lastSmaller = nums[i];
            } 
            maxLen = max(len, maxLen);
        }
        return maxLen;
    }
};

Time Complexity: O(nlogn) + O(n)

Space Complexity: O(1)

Optimal Approach#

Load all elements into an unordered set for O(1) average-case lookups. A sequence can only be counted efficiently if we start from its smallest element, so we process an element x as a sequence start only when x-1 is absent from the set. Then we count upward (x+1, x+2, ...) via set lookups until the sequence breaks. Because each element is visited at most once as a start or as part of a count, the total work is O(n) amortised — beating the sorting approach at the cost of O(n) extra space for the set.

• Use set to track the elements
• Find start of the sequence and check consecutive element presence in set

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st;
        for(int num:nums)
            st.insert(num);

        int maxLen = 0;
        for(int num:st){
            if(!st.count(num-1)){
                int curr = num;
                int streak = 1;

                while(st.count(curr+1)){
                    curr++;
                    streak++;
                }

                maxLen = max(maxLen, streak);
            }
        }
        return maxLen;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)