Longest Consecutive Sequence in Arrays

Introduction

• Commonly asked in coding interviews (e.g., Google)
• Problem: Find the longest consecutive sequence in an input array of numbers
  • Example: For array [100, 4, 200, 1, 3, 2], the longest consecutive sequence is 1-2-3-4

Basic Approach (Sorting)

• Method: Sort the array and check consecutive elements
• Example:
  • Sorted Array: [1, 2, 3, 4, 100, 200]
  • Consecutive Sequences: 1-2-3-4, 100, 200
• Drawback: Time Complexity is O(N log N)

Optimized Approach

• Visualization: Draw a number line for better human-like problem-solving
  • Identify distinct sequences
  • Sequence start has no left neighbor
• Key Insight: Identify start of sequence efficiently

Efficient Method

• Use a Set to check for neighbors (lookup is O(1))
• Iterate through array to find sequence starts (elements without left neighbors)
• Steps:
  1. Convert array to a Set
  2. Iterate through each number
  3. Check if a number is the start of a sequence
  4. If start, find the length of the sequence by checking consecutive numbers

Implementing the Solution

• Create a Set: num_set = set(nums)
• Initialize longest variable: longest = 0
• Iterate and check:
  1. For every number n in nums:
  2. Check if n-1 is not in num_set
  3. If true, initialize length = 0 and check for consecutive numbers
  4. Update the length of the sequence
  5. Update longest

Code Example in Python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        longest = 0
        for n in nums:
            if (n - 1) not in num_set:
                length = 0
                while (n + length) in num_set:
                    length += 1
                longest = max(longest, length)
        return longest

Conclusion

• Efficiency: Linear time complexity O(N) and linear space complexity O(N)
• Visualizing the problem simplifies deriving the solution.
• Only iterates through each number at most twice.