Longest Consecutive Sequence in Array

Given an unsorted array of integers, your task is to find the length of the longest sequence of consecutive numbers that appear in the array.

• A consecutive sequence is a group of numbers where each number is exactly 1 more than the previous number.
• The numbers in the array can be in any order and may contain duplicates.
• You need to return the length of the longest such sequence.

If the array is empty, return 0.

Understanding the Problem

We are given an unsorted array of integers, and our goal is to find the length of the longest sequence of consecutive numbers that can be formed from the array.

A consecutive sequence means numbers that follow one after another, like [3, 4, 5, 6]. The order of elements in the input array doesn't matter, and we must only use unique numbers to form such sequences.

Step-by-Step Breakdown with Example

Example: [100, 4, 200, 1, 3, 2]

Let’s try to visualize the sequences hidden in this array:

• From 1, we can find 2, 3, and 4 — a sequence of length 4.
• Other numbers like 100 and 200 are standalone.

So the longest consecutive chain is [1, 2, 3, 4], and the answer is 4.

Exploring Edge Cases

Case 1: Fully Ordered Array

[1, 2, 3, 4, 5] — Already a full sequence. We return 5.

Case 2: With Duplicates

[5, 5, 5] — We ignore duplicates. Only one unique number means a sequence length of 1.

Case 3: Gapped Numbers

[10, 30, 50] — No two numbers are consecutive. Each number stands alone, so the answer is 1.

Case 4: Empty Array

[] — No elements, hence no sequence. Return 0.

Our Strategy to Solve It

We solve the problem efficiently by using a Set to store all the unique numbers from the array. This helps in:

• Removing duplicates automatically
• Allowing O(1) lookups when checking for consecutive elements

For each number in the set, we check whether it could be the start of a new sequence — this is true if num - 1 does not exist in the set.

If it's a valid start, we then check for num + 1, num + 2, and so on, to count the length of that sequence. We track the maximum sequence length found during this process.

Each number is checked only once — either as a starting point or ignored if already part of a longer sequence. This means we never do redundant work.

1. Given an unsorted array arr of integers.
2. Insert all elements into a HashSet for constant-time lookups.
3. Initialize max_length = 0.
4. For each element num in arr:
5. → Check if num - 1 is not in the set (meaning num is the start of a new sequence).
6. → If so, initialize current_length = 1 and incrementally check for num + 1, num + 2, ... while they exist in the set, incrementing current_length.
7. → Update max_length with the maximum of max_length and current_length.
8. Return max_length.

#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 10007

int hashSet[HASH_SIZE];

int contains(int num) {
    return hashSet[abs(num) % HASH_SIZE] == num;
}

void insert(int num) {
    hashSet[abs(num) % HASH_SIZE] = num;
}

int longestConsecutive(int* arr, int n) {
    for (int i = 0; i < HASH_SIZE; i++) hashSet[i] = -1;
    for (int i = 0; i < n; i++) insert(arr[i]);

    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        if (!contains(arr[i] - 1)) {
            int current = arr[i];
            int length = 1;
            while (contains(current + 1)) {
                current++;
                length++;
            }
            if (length > maxLength) maxLength = length;
        }
    }
    return maxLength;
}

int main() {
    int arr[] = {100, 4, 200, 1, 3, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Longest Consecutive Sequence Length: %d\n", longestConsecutive(arr, n));
    return 0;
}

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

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    int maxLength = 0;

    for (int num : nums) {
        if (!numSet.count(num - 1)) {
            int current = num;
            int length = 1;

            while (numSet.count(current + 1)) {
                current++;
                length++;
            }

            maxLength = max(maxLength, length);
        }
    }
    return maxLength;
}

int main() {
    vector<int> arr = {100, 4, 200, 1, 3, 2};
    cout << "Longest Consecutive Sequence Length: " << longestConsecutive(arr) << endl;
    return 0;
}

def longest_consecutive_sequence(arr):
    num_set = set(arr)
    max_length = 0
    
    for num in arr:
        if num - 1 not in num_set:
            current = num
            length = 1
            while current + 1 in num_set:
                current += 1
                length += 1
            max_length = max(max_length, length)

    return max_length

# Sample Input
arr = [100, 4, 200, 1, 3, 2]
print("Longest Consecutive Sequence Length:", longest_consecutive_sequence(arr))

import java.util.HashSet;

public class LongestConsecutive {
    public static int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);

        int maxLength = 0;

        for (int num : nums) {
            if (!set.contains(num - 1)) {
                int current = num;
                int length = 1;

                while (set.contains(current + 1)) {
                    current++;
                    length++;
                }

                maxLength = Math.max(maxLength, length);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] arr = {100, 4, 200, 1, 3, 2};
        System.out.println("Longest Consecutive Sequence Length: " + longestConsecutive(arr));
    }
}

function longestConsecutiveSequence(arr) {
    const numSet = new Set(arr);
    let maxLength = 0;

    for (let num of arr) {
        if (!numSet.has(num - 1)) {
            let current = num;
            let length = 1;

            while (numSet.has(current + 1)) {
                current++;
                length++;
            }

            maxLength = Math.max(maxLength, length);
        }
    }

    return maxLength;
}

// Sample Input
const arr = [100, 4, 200, 1, 3, 2];
console.log('Longest Consecutive Sequence Length:', longestConsecutiveSequence(arr));

package main

import (
    "fmt"
)

func longestConsecutive(nums []int) int {
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }

    maxLength := 0
    for _, num := range nums {
        if !numSet[num-1] {
            current := num
            length := 1
            for numSet[current+1] {
                current++
                length++
            }
            if length > maxLength {
                maxLength = length
            }
        }
    }
    return maxLength
}

func main() {
    arr := []int{100, 4, 200, 1, 3, 2}
    fmt.Println("Longest Consecutive Sequence Length:", longestConsecutive(arr))
}

use std::collections::HashSet;

fn longest_consecutive(nums: Vec<i32>) -> i32 {
    let num_set: HashSet<i32> = nums.iter().cloned().collect();
    let mut max_length = 0;

    for &num in &nums {
        if !num_set.contains(&(num - 1)) {
            let mut current = num;
            let mut length = 1;
            while num_set.contains(&(current + 1)) {
                current += 1;
                length += 1;
            }
            max_length = max_length.max(length);
        }
    }
    max_length
}

fn main() {
    let arr = vec![100, 4, 200, 1, 3, 2];
    println!("Longest Consecutive Sequence Length: {}", longest_consecutive(arr));
}

fun longestConsecutive(nums: IntArray): Int {
    val numSet = nums.toHashSet()
    var maxLength = 0

    for (num in nums) {
        if (!numSet.contains(num - 1)) {
            var current = num
            var length = 1
            while (numSet.contains(current + 1)) {
                current++
                length++
            }
            maxLength = maxOf(maxLength, length)
        }
    }
    return maxLength
}

fun main() {
    val arr = intArrayOf(100, 4, 200, 1, 3, 2)
    println("Longest Consecutive Sequence Length: ${longestConsecutive(arr)}")
}

import Foundation

func longestConsecutive(_ nums: [Int]) -> Int {
    let numSet = Set(nums)
    var maxLength = 0

    for num in nums {
        if !numSet.contains(num - 1) {
            var current = num
            var length = 1
            while numSet.contains(current + 1) {
                current += 1
                length += 1
            }
            maxLength = max(maxLength, length)
        }
    }
    return maxLength
}

let arr = [100, 4, 200, 1, 3, 2]
print("Longest Consecutive Sequence Length: \(longestConsecutive(arr))")

function longestConsecutiveSequence(arr: number[]): number {
    const numSet = new Set(arr);
    let maxLength = 0;

    for (const num of arr) {
        if (!numSet.has(num - 1)) {
            let current = num;
            let length = 1;

            while (numSet.has(current + 1)) {
                current++;
                length++;
            }
            maxLength = Math.max(maxLength, length);
        }
    }
    return maxLength;
}

const arr: number[] = [100, 4, 200, 1, 3, 2];
console.log("Longest Consecutive Sequence Length:", longestConsecutiveSequence(arr));

Time complexity

Space complexity

O(n)

A HashSet is used to store all unique elements of the array for quick lookups, which requires linear space in terms of the input size.