128. Longest Consecutive Sequence - Leetcode Solution

LeetCode problem Solution code

đź’ˇ Step-by-Step Thought Process

  1. Understand the problem: Find the length of the longest consecutive sequence in an array of integers.
  2. Convert the input array nums into a set s for O(1) lookups.
  3. Initialize longest to 0 to track the length of the longest sequence.
  4. Iterate through each number num in the set s.
  5. Check if num - 1 is not in s, indicating num could be the start of a sequence.
  6. If true, set next_num to num + 1 and length to 1 for the current sequence.
  7. While next_num is in s, increment length and next_num to extend the sequence.
  8. Update longest to the maximum of longest and the current length.
  9. Return longest as the result.

Code Solution

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        longest = 0

        for num in s:
            if num - 1 not in s:
                next_num = num + 1
                length = 1
                while next_num in s:
                    length += 1
                    next_num += 1
                longest = max(longest, length)
        
        return longest

# Time Complexity: O(n)
# Space Complexity: O(n)

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

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> set(nums.begin(), nums.end());
        int longest = 0;

        for (int num : set) {
            if (set.find(num - 1) == set.end()) {
                int length = 1;
                int nextNum = num + 1;
                while (set.find(nextNum) != set.end()) {
                    length++;
                    nextNum++;
                }
                longest = max(longest, length);
            }
        }

        return longest;
    }
};

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

public class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int longest = 0;

        for (int num : set) {
            if (!set.contains(num - 1)) {
                int length = 1;
                int nextNum = num + 1;
                while (set.contains(nextNum)) {
                    length++;
                    nextNum++;
                }
                longest = Math.max(longest, length);
            }
        }

        return longest;
    }
}

var longestConsecutive = function(nums) {
    const set = new Set(nums);
    let longest = 0;

    for (const num of set) {
        if (!set.has(num - 1)) {
            let length = 1;
            let nextNum = num + 1;
            while (set.has(nextNum)) {
                length++;
                nextNum++;
            }
            longest = Math.max(longest, length);
        }
    }

    return longest;
};

Detailed Explanation

Understanding the Problem: Longest Consecutive Sequence

The “Longest Consecutive Sequence” problem asks us to find the length of the longest sequence of consecutive integers that can be formed from a given array of integers. The numbers in the sequence do not need to appear in order in the array, and duplicates should be ignored.

For example:

  • Input: [100, 4, 200, 1, 3, 2] → Output: 4 (the sequence is [1, 2, 3, 4])
  • Input: [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] → Output: 9 (the sequence is [0–8])

Why This Problem Matters

This problem is commonly used to test your ability to optimize brute-force logic and efficiently track patterns using hash-based data structures. It teaches techniques in sequence construction, set-based lookup, and one-pass logic to eliminate redundancy.

Efficient Approach Using a Set

The brute-force solution using sorting would require O(n log n) time. However, the optimal solution leverages a set for O(1) lookups, allowing us to solve the problem in O(n) time.

Steps:

  1. Convert the input array into a set to eliminate duplicates and allow constant-time lookups.
  2. Initialize a variable longest to track the length of the longest sequence found.
  3. Loop through each number num in the set:
    • Only start a sequence from num if num - 1 is not in the set. This ensures we only begin from the beginning of a potential sequence.
    • Initialize currentLength = 1 and currentNum = num + 1.
    • While currentNum is in the set, increment currentLength and currentNum.
    • Update longest to the maximum of itself and currentLength.
  4. After the loop, return longest.

Example Walkthrough

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

  • Converted set: {1, 2, 3, 4, 100, 200}
  • Start at 1 → check 2, 3, 4 → length = 4
  • 100 and 200 are standalone → no longer sequence found
  • Return: 4

Time and Space Complexity

Time Complexity: O(n), where n is the number of elements in the array. Each element is processed at most twice (once in the loop, once in the inner sequence).
Space Complexity: O(n), due to storing the elements in a set.

Edge Cases to Consider

  • Empty array → return 0
  • Array with one number → return 1
  • Array with all duplicates → still count as a sequence of 1
  • Already sorted input → works efficiently without extra sorting

Conclusion

The “Longest Consecutive Sequence” problem is a great example of replacing brute-force logic with a hash set to achieve optimal time complexity. It rewards careful iteration and teaches the power of only initiating work when it is necessary — a valuable lesson in writing efficient algorithms.

NEW!Need help landing software roles? đź’ˇ