Skip to main content

Longest Consecutive Sequence

Question​

Given an unsorted array of integers, find the length of the longest consecutive sequence of integers within the array.

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

Output: [1, 2, 3, 4]

Solution​

all//Longest Consecutive Sequence.py


def longestConsecutiveSequence(arr):
    s = set()
    for element in arr:
        s.add(element)

    longest_sequence = 0
    start = 0
    end = 0

    for i in range(len(arr)):
        if (arr[i] - 1) not in s:
            j = arr[i]
            while (j in s):
                j += 1

            if longest_sequence < j - arr[i]:
                longest_sequence = j - arr[i]
                start = arr[i]
                end = j - 1

    output = []
    for i in range(start, end + 1):
        output.append(i)
    return output

# Driver code
arr = [3, 10, 5, 11, 6, 4, 12, 7]
print(longestConsecutiveSequence(arr))