Input: nums = [1, 6, 2, 5, 8, 7, 10, 3]
Output: 4

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition

A naive approach to this problem is to sort the array. When all numbers are arranged in ascending order, consecutive numbers will be placed next to each other. This allows us to iterate through the array to identify the longest sequence of consecutive numbers.

This approach requires sorting, which takes $O(n\log (n))$ time, where $n$ denotes the length of the array. Let’s see how we could do better.

It’s important to understand that every number in the array can represent the start of some consecutive chain. One approach is to treat each number as the start of a chain and search through the array to identify the rest of its chain.

To do this, we can leverage the fact that for any number num, its next consecutive number will be num + 1. This means we’ll always know which number to look for when trying to find the next number in a sequence. The code snippet for this approach is provided below:

from typing import List
     
def longest_chain_of_consecutive_numbers_brute_force(nums: List[int]) -> int:
    if not nums:
        return 0
    longest_chain = 0
    # Look for chains of consecutive numbers that start from each number.
    for num in nums:
        current_num = num
        current_chain = 1
        # Continue to find the next consecutive numbers in the chain.
        while (current_num + 1) in nums:
            current_num += 1
            current_chain += 1
        longest_chain = max(longest_chain, current_chain)
    return longest_chain

#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int longestChainOfConsecutiveNumbersBruteForce(vector<int>& nums) {
    if (nums.empty()) return 0;
    set<int> unique(nums.begin(), nums.end());   // sorted + de-duped
    vector<int> values(unique.begin(), unique.end());
    int longest = 1, current = 1;
    for (size_t i = 1; i < values.size(); i++) {
        if (values[i] == values[i - 1] + 1) {
            current++;                   // run continues
        } else {
            current = 1;                 // run broke; start over
        }
        longest = max(longest, current);
    }
    return longest;
}

import java.util.*;

public int longestChainOfConsecutiveNumbersBruteForce(int[] nums) {
    if (nums.length == 0) return 0;
    TreeSet<Integer> set = new TreeSet<>();   // sorted + de-duped
    for (int x : nums) set.add(x);
    int longest = 1, current = 1;
    boolean first = true;
    int prev = 0;
    for (int x : set) {
        if (!first && x == prev + 1) {
            current++;                   // run continues
        } else {
            current = 1;                 // run broke (or first value)
        }
        first = false;
        prev = x;
        longest = Math.max(longest, current);
    }
    return longest;
}

This brute force approach takes $O(n^3)$ time because of the nested operations involved:

• The outer for-loop iterates through each element, which takes $O(n)$ time.

• For each element, the inner while-loop can potentially run up to n iterations if there is a long consecutive sequence starting from the current number.

• For each, while-loop iteration, an $O(n)$ check is performed to see if the next consecutive number exists in the array.

This is slower than the sorting approach, but we can make a couple of optimizations to improve the time complexity. Let’s discuss these.

Optimization - hash set
To find the next number in a sequence, we perform a linear search through the array. However, by storing all the numbers in a hash set, we can instead query this hash set in constant time to check if a number exists.

This reduces the time complexity from $O(n^3)$ to $O(n^2)$.

Optimization - identifying the start of each chain
In the brute force approach, we treat each number as the start of a chain. This becomes quite expensive because we perform a linear search for every number to find the rest of its chain:

The key observation here is that we don’t need to perform this search for every number in a chain. Instead, we only need to perform it for the smallest number in each chain since this number identifies the start of its chain:

We can determine if a number is the smallest number in its chain by checking the array doesn’t contain the number that precedes it (curr_num - 1). We can also use the hash set for this check.

This reduces the time complexity from $O(n^2)$ to $O(n)$, as now every chain is searched through only once. This is explained in more detail in the complexity analysis.

Implementation

from typing import List
        
def longest_chain_of_consecutive_numbers(nums: List[int]) -> int:
    if not nums:
        return 0
    num_set = set(nums)
    longest_chain = 0
    for num in num_set:
        # If the current number is the smallest number in its chain, search for
        # the length of its chain.
        if num - 1 not in num_set:
            current_num = num
            current_chain = 1
            # Continue to find the next consecutive numbers in the chain.
            while current_num + 1 in num_set:
                current_num += 1
                current_chain += 1
            longest_chain = max(longest_chain, current_chain)
    return longest_chain

#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

int longestChainOfConsecutiveNumbers(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    int longest = 0;
    for (int num : numSet) {
        if (numSet.count(num - 1) == 0) {    // num starts a chain
            int length = 1;
            while (numSet.count(num + length)) {
                length++;
            }
            longest = max(longest, length);
        }
    }
    return longest;
}

import java.util.*;

public int longestChainOfConsecutiveNumbers(int[] nums) {
    Set<Integer> numSet = new HashSet<>();
    for (int num : nums) {
        numSet.add(num);                 // build set (dedupes too)
    }
    int longest = 0;
    for (int num : numSet) {
        if (!numSet.contains(num - 1)) { // num starts a chain
            int length = 1;
            while (numSet.contains(num + length)) {
                length++;
            }
            longest = Math.max(longest, length);
        }
    }
    return longest;
}

Complexity Analysis

Time complexity: The time complexity of longest_chain_of_consecutive_numbers is $O(n)$ because, although there are two loops, the inner loop is only executed when the current number is the start of a chain. This ensures that each chain is iterated through only once in the inner while-loop. Thus, the total number of iterations for both loops combined is $O(n)$: the outer for-loop runs $n$ times, and the inner while-loop runs a total of $n$ times across all iterations, resulting in a combined time complexity of $O(n+n)=O(n)$.

Space complexity: The space complexity is $O(n)$ since the hash set stores each unique number from the array.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language