Longest Consecutive Sequence

Master this topic with zero to advance depth.

Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in $O(n)$ time.

Visual Representation

nums = [100, 4, 200, 1, 3, 2]

Step 1: Put all in HashSet: {100, 4, 200, 1, 3, 2}
Step 2: Check each number if it's a START (num-1 not in set):
   - 100: (99? No) -> Start! Count 101, 102... (Len: 1)
   - 4:   (3? Yes) -> Not a start.
   - 200: (199? No) -> Start! Count 201... (Len: 1)
   - 1:   (0? No)  -> Start! Count 2, 3, 4 (Len: 4) -> MAX!

Medium

Examples

Input: nums = [100,4,200,1,3,2]
Output: 4
The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
The longest consecutive elements sequence is [0,1,2,3,4,5,6,7,8].

Approach 1

Level I: Brute Force (Check Each Number)

Intuition

For every number x in the array, we check if it is the start of a sequence by trying to find x+1, x+2, etc., using a linear scan through the array for each step. This leads to a cubic time complexity.

⏱ O(N³) because we have a loop for each number, a loop for the sequence length, and a linear scan `contains` check.💾 O(1)

Detailed Dry Run

Num	Sequence	Max Length
100	[100] (101 not found)	1
4	[4] (5 not found)	1
1	[1, 2, 3, 4]	4

java

import java.util.*;

public class Main {
    private static boolean contains(int[] nums, int target) {
        for (int n : nums) if (n == target) return true;
        return false;
    }
    
    public static int longestConsecutive(int[] nums) {
        int longest = 0;
        for (int num : nums) {
            int curr = num;
            int streak = 1;
            while (contains(nums, curr + 1)) {
                curr++;
                streak++;
            }
            longest = Math.max(longest, streak);
        }
        return longest;
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums));
    }
}

Approach 2

Level II: Better Solution (Sorting)

Intuition

By sorting the array, consecutive numbers are placed adjacent to each other. We can then find sequences by comparing each element with its predecessor. We must handle duplicate elements by skipping them during the streak calculation.

⏱ O(N log N) dominated by sorting the array.💾 O(1) (or O(N) depending on sort implementation).

Detailed Dry Run

Sorted Array	Comparison	Action	Streak
[1, 2, 3, 4, 100, 200]	2 == 1+1	Increment	2
[1, 2, 3, 4, 100, 200]	100 != 4+1	Reset	1

java

import java.util.*;

public class Main {
    public static int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Arrays.sort(nums);
        int longest = 1, curr = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) continue;
            if (nums[i] == nums[i-1] + 1) curr++;
            else {
                longest = Math.max(longest, curr);
                curr = 1;
            }
        }
        return Math.max(longest, curr);
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums));
    }
}

Approach 3

Level III: Optimal Solution (HashSet)

Intuition

To achieve linear time, we use a Hash Set for $O(1)$ lookups. The key insight is identifying the start of a sequence: a number x is the start if x-1 does not exist in the set. Only then we explore the sequence using a while loop, ensuring each element is visited at most twice.

⏱ O(N) because each number is visited at most twice (once in the main loop and once in a `while` loop).💾 O(N) to store the elements in the Hash Set.

Detailed Dry Run

Start-of-Sequence Logic

Number	x-1 In Set?	Action	Streak
100	99 (No)	Start Streak	1
4	3 (Yes)	Skip (not start)	-
1	0 (No)	Start Streak	4 (1,2,3,4)

Visual: [1] -> [2] -> [3] -> [4] (Sequence identified from 1)

java

import java.util.*;

public class Main {
    public static int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int longest = 0;
        for (int n : set) {
            if (!set.contains(n - 1)) { // Only start if it's the beginning
                int curr = n, streak = 1;
                while (set.contains(curr + 1)) {
                    curr++; streak++;
                }
                longest = Math.max(longest, streak);
            }
        }
        return longest;
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums));
    }
}

← Previous QuestionGroup Anagrams

Next Question →Product of Array Except Self

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.