Longest Consecutive Sequence

Medium Arrays

Find the length of the longest run of consecutive integers in an unsorted array in O(n) using a hash set (only start numbers grow a streak).

Sample input

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

Sample output

Solution

def longest_consecutive(nums):
    num_set = set(nums)
    best = 0
    for num in num_set:
        if num - 1 not in num_set:
            length = 1
            while num + length in num_set:
                length += 1
            best = max(best, length)
    return best

print(longest_consecutive([100, 4, 200, 1, 3, 2]))

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const num of set) {
    if (!set.has(num - 1)) {
      let length = 1;
      while (set.has(num + length)) length++;
      best = Math.max(best, length);
    }
  }
  return best;
}

console.log(longestConsecutive([100, 4, 200, 1, 3, 2]));

import java.util.HashSet;
import java.util.Set;

public class Main {
    static int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        int best = 0;
        for (int num : set) {
            if (!set.contains(num - 1)) {
                int length = 1;
                while (set.contains(num + length)) length++;
                best = Math.max(best, length);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));
    }
}

fun longestConsecutive(nums: IntArray): Int {
    val set = nums.toHashSet()
    var best = 0
    for (num in set) {
        if (num - 1 !in set) {
            var length = 1
            while (num + length in set) length++
            best = maxOf(best, length)
        }
    }
    return best
}

fun main() {
    println(longestConsecutive(intArrayOf(100, 4, 200, 1, 3, 2)))
}

func longestConsecutive(_ nums: [Int]) -> Int {
    let set = Set(nums)
    var best = 0
    for num in set {
        if !set.contains(num - 1) {
            var length = 1
            while set.contains(num + length) { length += 1 }
            best = max(best, length)
        }
    }
    return best
}

print(longestConsecutive([100, 4, 200, 1, 3, 2]))

int longestConsecutive(List<int> nums) {
  final set = nums.toSet();
  int best = 0;
  for (final num in set) {
    if (!set.contains(num - 1)) {
      int length = 1;
      while (set.contains(num + length)) length++;
      if (length > best) best = length;
    }
  }
  return best;
}

void main() {
  print(longestConsecutive([100, 4, 200, 1, 3, 2]));
}

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

int longestConsecutive(const vector<int>& nums) {
    unordered_set<int> set(nums.begin(), nums.end());
    int best = 0;
    for (int num : set) {
        if (set.find(num - 1) == set.end()) {
            int length = 1;
            while (set.find(num + length) != set.end()) length++;
            best = max(best, length);
        }
    }
    return best;
}

int main() {
    cout << longestConsecutive({100, 4, 200, 1, 3, 2}) << endl;
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(const int *) a) - (*(const int *) b);
}

int main() {
    int nums[] = {100, 4, 200, 1, 3, 2};
    int n = 6;
    qsort(nums, n, sizeof(int), cmp);
    int best = 1, length = 1;
    for (int i = 1; i < n; i++) {
        if (nums[i] == nums[i - 1]) continue;
        if (nums[i] == nums[i - 1] + 1) length++;
        else length = 1;
        if (length > best) best = length;
    }
    printf("%d\n", best);
    return 0;
}