Longest Consecutive Sequence

 Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

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

 

Example 1:

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

Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

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

Output: 9

Example 3:

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

Output: 3

 

✅ Step-by-Step Dry Run:

---

🔹 Step 1: Put all numbers into a set

We create this:

set = {100, 4, 200, 1, 3, 2}

So we can quickly check if a number exists (in O(1) time).

🔹 Step 2: Loop through each number in the array

🔸 First number: 100

• Check if 99 is in the set → ❌ No

• So 100 is the start of a sequence

• Start counting:

  • 101 → ❌ not in set → Stop

• Sequence length = 1

• longest = max(0, 1) = 1

• 🔸 Next: 4

  • Check if 3 is in the set → ✅ Yes

  • So 4 is not a starting point → skip

  🔸 Next: 200

• Check if 199 is in the set → ❌ No

• So 200 is a start of a sequence

• Check 201 → ❌ Not in set → Stop

• Sequence length = 1

• longest = max(1, 1) = 1

• 🔸 Next: 1

  • Check if 0 is in the set → ❌ No

  • So 1 is a start of a sequence

  • Start counting:

    • 2 → ✅

    • 3 → ✅

    • 4 → ✅

    • 5 → ❌ Stop

  • Sequence = 1, 2, 3, 4 → Length = 4

  • longest = max(1, 4) = 4

  
  

•  Next: 3

  • Check if 2 is in the set → ✅ Yes

  • So 3 is not the start → skip

  
  

 Next: 2

• Check if 1 is in the set → ✅ Yes

• So 2 is not the start → skip

Final Answer:

return longest; // 4

Brute Force :

class Solution {

    public int longestConsecutive(int[] nums) {

       

    Arrays.sort(nums);

    if(nums.length==0)

    return 0;

    int maxi=1;

    int count=1;

for(int i=1;i<nums.length;i++)

{

    if(nums[i]==nums[i-1])

    {

        continue;//skip duplicate

    }

    if(nums[i]==nums[i-1]+1)

    {

        count++;

    }

    else

    {

        maxi=Math.max(maxi,count);

        count=1;

    }

}

 maxi=Math.max(maxi,count);

return maxi;

    }

}

Better Approach:

class Solution {

    public int longestConsecutive(int[] nums) {

          HashSet<Integer> set = new HashSet<>();

        for (int num : nums) {

            set.add(num);

        }

        int maxLen = 0;

        for (int num : set) {

            // Only start counting if num is the start of a sequence

            if (!set.contains(num - 1)) {

                int current = num;

                int count = 1;

                while (set.contains(current + 1)) {

                    current++;

                    count++;

                }

                maxLen = Math.max(maxLen, count);

            }

        }

        return maxLen;

    }

}