_128. Longest Consecutive Sequence.md

128. Longest Consecutive Sequence

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 13, 2024

Last updated : March 12, 2025

---

Related Topics : Array, Hash Table, Union Find

Acceptance Rate : 47.17 %

---

m128 v1

My initial attempt that was successful but inefficient. Achieved around a 350ms runtime.

m128 java

Second attempt that was much more successful and achieved a reasonable runtim

m128 v2

2nd python attempt that implemented a set removal optimization to save redundancy that brought the python version to the same runtime level as java.

---

Solutions

• m128 v1.py
• m128 v2.py
• m128.java

Python

m128 v1.py

# O(n) solution babyyyy

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0 :
            return 0
        
        vals = set(nums)                # O(n) creation, O(1) lookups

        maxx = 0
        for val in vals:                # O(n) looping
            if val - 1 in vals:         # not start of sequence
                continue
            
            cnter = 1
            while val + cnter in vals :
                cnter += 1

            maxx = max(maxx, cnter)

        return maxx

m128 v2.py

# O(n) solution babyyyy

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0 :
            return 0

        vals = set(nums)                # O(n) creation, O(1) lookups

        maxx = 0
        while vals :
            left = right = vals.pop()
            curr = 1
            while left - 1 in vals :
                left -= 1
                curr += 1
                vals.remove(left)
            while right + 1 in vals :
                right += 1
                curr += 1
                vals.remove(right)

            maxx = max(maxx, curr)

        return maxx

Java

m128.java

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> vals = new HashSet<>();

        for (int n : nums) {
            vals.add(n);
        }

        int maxCounter = 0;
        for (int n : vals) {
            if (vals.contains(n - 1)) {
                continue;
            }

            int counter = 1;
            while (vals.contains(n + counter)) {
                counter++;
            }

            if (counter > maxCounter) {
                maxCounter = counter;
            }

        }
        return maxCounter;
    }
}