Find Longest Consecutive Sequence in an Array - Visualization

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

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.

Examples❯

Input Array Longest Consecutive Sequence Length Description
[100, 4, 200, 1, 3, 2] [1, 2, 3, 4] 4 Longest consecutive sequence starts at 1 and ends at 4
[0, 3, 7, 2, 5, 8, 4, 6, 0, 1] [0, 1, 2, 3, 4, 5, 6, 7, 8] 9 All elements from 0 to 8 form the longest consecutive sequence
[10, 30, 20] [10] 1 No two numbers are consecutive, so each number alone is a sequence
[1, 9, 3, 10, 2, 20] [1, 2, 3] 3 Consecutive sequence from 1 to 3
[5, 5, 5, 5] [5] 1 All elements are duplicates, so only one unique number exists
[] [] 0 Empty array, no sequence exists

Solution❯

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.

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, each element is checked only once, and very few sequences are formed. The HashSet operations are constant time on average.
Average CaseO(n)Each number is visited once when building the set and at most once again when scanning for sequence starts, resulting in linear time.
Worst CaseO(n)Even in the worst case, each element is processed at most twice—once during insertion and once during sequence scanning. So time remains linear.

Space Complexity❯

O(n)

Explanation: 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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...