ProgramGuru.org

ProgramGuru.org

Longest Consecutive Sequence in Array - Optimal Approach

Longest Consecutive Sequence in Array - Optimal Approach

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.

Find Longest Consecutive Sequence in Array using HashSet Code

Python
JavaScript
Java
C++
C
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))