coding

🚀 Fixing Time Limit Exceeded in “Longest Consecutive Sequence” (LeetCode 128)

Pandiyan MuruganLeave a comment

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.

Understanding Arrays in C#

Pandiyan MuruganLeave a comment

Arrays are a fundamental data structure in C#, allowing you to store multiple values of the same type in a single variable. They provide a way to efficiently manage and access collections of data. In this blog, we’ll explore different ways to declare, initialize, and use arrays in C#.

Declaring and Initializing Arrays

1. Basic Array Declaration

You can declare an array in C# by specifying the type and size:

int[] numbers = new int[5]; // Creates an array of size 5 with default values (0)

This initializes an array with five elements, all set to the default value of 0.

2. Array with Predefined Values

You can also initialize an array with predefined values:

int[] numbers = { 1, 2, 3, 4, 5 };

Or explicitly using new:

int[] numbers = new int[] { 1, 2, 3, 4, 5 };

Multidimensional Arrays

C# supports multidimensional arrays, such as 2D arrays:

int[,] matrix = new int[2, 3] { { 1, 2, 3 }, { 4, 5, 6 } };

This creates a 2×3 matrix.

Jagged Arrays

A jagged array is an array of arrays, where each sub-array can have a different length:

int[][] jaggedArray = new int[3][];
jaggedArray[0] = new int[] { 1, 2 };
jaggedArray[1] = new int[] { 3, 4, 5 };
jaggedArray[2] = new int[] { 6 };

Can We Have an Array Without a Fixed Size?

Unlike lists, arrays in C# require a fixed size at the time of declaration. You must specify the size when using new:

int[] numbers = new int[5]; // Valid

If you need a dynamically sized collection, use List<T>:

List<int> numbers = new List<int>();
numbers.Add(1);
numbers.Add(2);
numbers.Add(3);
Console.WriteLine(numbers.Count); // Output: 3

Accessing and Modifying Array Elements

You can access and modify elements using an index:

int[] numbers = { 10, 20, 30, 40, 50 };
numbers[1] = 25; // Modifies the second element
Console.WriteLine(numbers[1]); // Output: 25

Iterating Over Arrays

Using a for loop:

for (int i = 0; i < numbers.Length; i++)
{
    Console.WriteLine(numbers[i]);
}

Using foreach:

foreach (int num in numbers)
{
    Console.WriteLine(num);
}

Conclusion

Arrays are a powerful tool in C#, offering efficient storage and access for collections of data. However, they require a fixed size, so for dynamic data structures, List<T> might be a better choice. Understanding arrays will help you build efficient and performant C# applications.

Happy coding! 🚀