Longest Consecutive Sequence

Published atDate not available

Array Medium 0 views

Like0

This problem asks for the length of the longest run of numbers that can stand next to each other in counting order, like 1, 2, 3, 4. The numbers do not need to sit next to each other in the original list, but they do need to form a consecutive sequence of values.

That means you are looking for the largest block where every number is exactly one more than the number before it. Duplicate values do not make the streak longer, and missing numbers break the streak. The answer is only the length of the best sequence, not the sequence itself.

For example, in [100,4,200,1,3,2], the best consecutive run is 1,2,3,4, so the answer is 4. In [0,3,7,2,5,8,4,6,0,1], the run from 0 to 8 appears, so the answer is 9. If the list is empty, the answer is 0.

The important thing is to think about value order, not original position order.

Example Input & Output

Example 1

Input

nums = []

Output

Explanation

Example with input: nums = []

Example 2

Input

nums = [0,3,7,2,5,8,4,6,0,1]

Output

Explanation

Example with input: nums = [0,3,7,2,5,8,4,6,0,1]

Example 3

Input

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

Output

Explanation

Example with input: nums = [100,4,200,1,3,2]

Algorithm Flow

Recommendation Algorithm Flow for Longest Consecutive Sequence

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int longest_consecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int maxLen = 0;
        for (int x : set) {
            if (!set.contains(x - 1)) {
                int current = x, streak = 1;
                while (set.contains(current + 1)) {
                    current++; streak++;
                }
                maxLen = Math.max(maxLen, streak);
            }
        }
        return maxLen;
    }
}

javascript

function longest_consecutive(nums) {
    if (nums.length === 0) return 0;
    const numSet = new Set(nums);
    let maxLen = 0;
    for (let x of numSet) {
        if (!numSet.has(x - 1)) {
            let current = x, streak = 1;
            while (numSet.has(current + 1)) {
                current++; streak++;
            }
            maxLen = Math.max(maxLen, streak);
        }
    }
    return maxLen;
}

php

function longest_consecutive($nums) {
    if (empty($nums)) return 0;
    $numSet = array_flip($nums);
    $maxLen = 0;
    foreach ($numSet as $x => $val) {
        if (!isset($numSet[$x - 1])) {
            $current = $x; $streak = 1;
            while (isset($numSet[$current + 1])) {
                $current++; $streak++;
            }
            $maxLen = max($maxLen, $streak);
        }
    }
    return $maxLen;
}

python

def longest_consecutive(nums: list) -> int:
    if not nums: return 0
    num_set = set(nums)
    max_len = 0
    for x in num_set:
        if x - 1 not in num_set:
            current = x
            streak = 1
            while current + 1 in num_set:
                current += 1
                streak += 1
            max_len = max(max_len, streak)
    return max_len

rust

use std::collections::HashSet;
pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
    if nums.is_empty() { return 0; }
    let set: HashSet<i32> = nums.into_iter().collect();
    let mut max_len = 0;
    for &x in &set {
        if !set.contains(&(x - 1)) {
            let mut current = x;
            let mut streak = 1;
            while set.contains(&(current + 1)) {
                current += 1;
                streak += 1;
            }
            max_len = std::cmp::max(max_len, streak);
        }
    }
    max_len
}

typescript

function longest_consecutive(nums: number[]): number {
    if (nums.length === 0) return 0;
    const numSet = new Set(nums);
    let maxLen = 0;
    for (let x of numSet) {
        if (!numSet.has(x - 1)) {
            let current = x, streak = 1;
            while (numSet.has(current + 1)) {
                current++; streak++;
            }
            maxLen = Math.max(maxLen, streak);
        }
    }
    return maxLen;
}

Related Array Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Longest Consecutive Sequence

Example Input & Output

Algorithm Flow

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Array Challenges

Garden Relay Count

Lantern Stall Picks

Festival Stall Order

Studio Lighting Slots

Seaport Ferry Gate Control

Railway Network Delay Optimizer

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.