Longest Consecutive Subsequence

Time: O(n)

Space: O(n)

Intuition

Add all elements to a HashSet. For each number n where n-1 is NOT in the set (it's a sequence start), count how long the streak goes.

Algorithm

1Add all nums to HashSet.
2For each n where set doesn't contain n-1: count streak = 1, while set contains n+streak: streak++.
3Update max streak.

Example Walkthrough

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

1.Start=1: 1,2,3,4 â†’ streak=4. Start=100: streak=1. Start=200: streak=1.

Output: 4

Common Pitfalls

•Only start counting from sequence start (n-1 not in set) â€” avoids O(nÂ²) repetition.

Longest Consecutive Subsequence.java

Java

// Approach: HashSet of all numbers. For each number that starts a sequence (n-1 not in set), extend the chain.
// Time: O(n) Space: O(n)
class Solution {

    // Function to return length of longest subsequence of consecutive integers.
    public int longestConsecutive(int[] arr) {
        if (arr.length == 0)
            return 0; // Handle edge case for empty array

        HashSet<Integer> set = new HashSet<>();
        int min = Integer.MAX_VALUE;
        int max = -1;

        for (int i : arr) {
            min = Math.min(min, i);
            max = Math.max(max, i);
            set.add(i);
        }

        int m = 1;
        int cnt = 1;
        for (int i = min; i < max; i++) {
            if (set.contains(i + 1))
                cnt++;
            else {
                m = Math.max(cnt, m);
                cnt = 0;
            }
        }
        
        return Math.max(cnt, m);
    }
}

Was this solution helpful?