Introduction

LeetCode’s Longest Consecutive Sequence problem challenges us to find the longest sequence of consecutive numbers in an unsorted array in O(n) time. My initial approach seemed correct but ran into Time Limit Exceeded (TLE) issues. After optimizing the code, I discovered that removing elements from the HashSet significantly improved performance. Let’s explore why!

---

My Initial (TLE) Solution

This solution checks each number and expands the sequence while map.Contains(num + length) remains true.

public class Solution {
    public int LongestConsecutive(int[] nums) {
        HashSet<int> map = new HashSet<int>(nums);
        int result = 0;

        foreach (int num in nums) {
            if (!map.Contains(num - 1)) { // Start of sequence
                int length = 0;
                while (map.Contains(num + length)) { 
                    length++;
                }
                result = Math.Max(result, length);
            }
        }
        return result;
    }
}

Why Does This Cause TLE?

🔴 Repeated Lookups: The while loop checks the same numbers multiple times.
🔴 Inefficient for Large Inputs: If the array is large, map.Contains(num + length) is called unnecessarily.

---

Optimized Solution (With set.Remove(currentNum))

Instead of checking the same numbers again, we remove elements from the set once we process them.

public class Solution {
    public int LongestConsecutive(int[] nums) {
        if (nums.Length == 0) return 0; // Handle empty array

        HashSet<int> set = new HashSet<int>(nums);
        int maxLength = 0;

        foreach (int num in nums) {
            if (!set.Contains(num - 1)) { // Start of sequence
                int currentNum = num;
                int length = 1;

                while (set.Contains(currentNum + 1)) {
                    currentNum++;
                    length++;
                    set.Remove(currentNum); // Remove to avoid rechecking
                }

                maxLength = Math.Max(maxLength, length);
            }
        }
        return maxLength;
    }
}

Why Does set.Remove(currentNum) Improve Performance?

✅ Each number is processed only once
✅ Avoids redundant Contains() lookups
✅ Reduces unnecessary iterations, ensuring O(n) complexity

By removing currentNum from set, we make sure that we never check the same number twice, significantly improving efficiency.

---

Time Complexity Analysis

• Initial approach: Worst-case O(n²) due to redundant lookups. ❌
• Optimized approach: O(n) since each number is visited only once. ✅

---

Final Thoughts

This simple fix—removing elements as they are processed—helps avoid unnecessary checks and reduces execution time drastically. If you’re facing TLE on LeetCode 128, adding set.Remove(currentNum) is the key! 🚀

What do you think? Have you faced similar performance issues? Let me know in the comments! 😊

Disclaimer: Code is fully written by me in this blog, but the text explaining the problem is generated with help of AI.