longest-consecutive-sequence.ts

/**
 * 128. Longest Consecutive Sequence  (Medium)
 * Link: https://leetcode.com/problems/longest-consecutive-sequence/
 *
 * Given an unsorted array, return the length of the longest run of consecutive
 * integers (e.g. 1,2,3,4). Must run in O(n).
 *
 * Example:
 *   Input:  nums = [100, 4, 200, 1, 3, 2]
 *   Output: 4            // 1, 2, 3, 4
 *
 * Approach:
 *   Put all numbers in a set for O(1) membership. Only start counting a run from
 *   a number that has no left neighbour (num - 1 absent) — that makes it a
 *   sequence start — then walk upward while the next value exists. Each number
 *   is visited at most twice, giving linear time despite the nested loop.
 *
 * Time:  O(n)
 * Space: O(n)
 */
export function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;

  for (const num of set) {
    if (set.has(num - 1)) continue; // not a sequence start

    let length = 1;
    let current = num;
    while (set.has(current + 1)) {
      current++;
      length++;
    }
    best = Math.max(best, length);
  }

  return best;
}