Longest Consecutive Sequence

You can arrange string anyways you need to return longest consecutive string,

Longest Consecutive Sequence

Problem

You are given an unsorted array of integers nums. Return the length of the longest consecutive sequence of numbers.

You must write an algorithm that runs in O(n) time.

A consecutive sequence is a group of numbers like 1, 2, 3, 4, where each number is exactly one more than the one before it. The numbers do not need to be next to each other in the array.

Examples

Example 1

Input: nums = [100,4,200,1,3,2]
Output: 4

• The longest consecutive sequence is [1, 2, 3, 4].
• Its length is 4.

Example 2

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

• The sequence is 0, 1, 2, 3, 4, 5, 6, 7, 8.

Example 3

Input: nums = [1,0,1,2]
Output: 3

• The sequence is 0, 1, 2.
• The duplicate 1 is counted only once.

Constraints

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Main Idea

The values can be as large as 10^9, so we cannot make an array with one cell for each value. We need another way.

Sorting idea

• Sort the array. Then consecutive numbers sit next to each other.
• Walk through the sorted array and count the length of each run.
• Skip duplicates, because they do not make a sequence longer.
• This is simple, but sorting takes O(n log n), so it does not meet the O(n) rule.

Set idea (optimal)

• Put all numbers in a Set. A Set checks "is this number here?" in O(1) time.
• A number is the start of a sequence if num - 1 is not in the set.
• For each start, count upward: num + 1, num + 2, ... while the numbers are in the set.
• Numbers that are not a start are skipped. They will be counted when we count from their start.

Why is this O(n)? The inner while loop runs only from a start. Each number is visited by the while loop at most once, because it belongs to only one sequence. So the total work is O(n), not O(n²).

Solution 1: Sorting

var longestConsecutive = function (nums) {
    if (nums.length === 0) return 0;

    nums.sort((a, b) => a - b);

    let streak = 1;
    let longestStreak = 1;

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) {
            // duplicate, skip it
            continue;
        } else if (nums[i] === nums[i - 1] + 1) {
            // the run continues
            streak++;
        } else {
            // the run is broken, start again
            streak = 1;
        }

        longestStreak = Math.max(longestStreak, streak);
    }

    return longestStreak;
};

Note: I removed the console.log(nums) line from your code. It prints the whole array and slows the code down.

How the Code Works

• If the array is empty, we return 0.
• sort((a, b) => a - b) sorts numbers by value. The default sort compares numbers as text, so we need (a, b) => a - b.
• streak is the length of the current run. longestStreak is the best run so far. Both start at 1.
• Duplicate: We use continue, so the run stays the same.
• Next number (previous + 1): The run grows by 1.
• Gap: The run is broken, so streak goes back to 1.
• After each step, we keep the maximum.

Dry Run

Let us take nums = [1, 0, 1, 2]. After sorting: [0, 1, 1, 2].

The answer is 3.

Complexity

• Time Complexity: O(n log n)
  • Sorting is the biggest cost. The loop takes O(n).
• Space Complexity: O(1) extra, or O(n) depending on the sort.
  • The sort works in place, but the engine may use extra memory.

Important: This solution works, but it does not meet the O(n) rule of the problem.

Solution 2: Set (Optimal)

function longestConsecutive(nums) {
    if (nums.length === 0) return 0;

    const set = new Set(nums);
    let longest = 1;

    for (let num of set) {
        // check if num is the start of a sequence
        if (!set.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;

            // count the length of the sequence
            while (set.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longest = Math.max(longest, currentStreak);
        }
    }

    return longest;
}

How the Code Works

• Step 1: new Set(nums) puts all numbers in a set. Duplicates are removed automatically.
• Step 2: We loop over the numbers in the set.
• Step 3: If num - 1 is in the set, num is in the middle of a sequence. We skip it.
• Step 4: If num - 1 is not in the set, num is a start. We count upward with the while loop, and currentStreak becomes the length of the sequence.
• Step 5: We keep the maximum in longest.

Dry Run

Let us take nums = [100, 4, 200, 1, 3, 2].

The set is {100, 4, 200, 1, 3, 2}.

The answer is 4.

Complexity

• Time Complexity: O(n)
  • Building the set takes O(n).
  • The while loop runs only from a sequence start, so each number is visited at most once in total.
  • Each has check takes O(1) on average.
• Space Complexity: O(n)
  • The set holds up to n numbers.

Comparison

Summary

• The values can be very large, so we cannot use an array indexed by value.
• Sorting works, but it takes O(n log n) time, so it does not meet the problem rule.
• The Set solution counts only from the start of each sequence, which is a number whose num - 1 is not in the set.
• Because of this, each number is counted once, and the total time is O(n).
• The Set also removes duplicates for us.
• The Set solution runs in O(n) time and uses O(n) space.