Day 6: Longest Consecutive Sequence

Problem Link:

Explore - LeetCode

Problem Statement:

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

Constraints:

- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9

Brute Force:

def longestConsecutiveSequence(A: List[int], n: int) -> int:
    longestStreak = 0
    for i in range (n):
        currentNum = A[i] - 1
        currentStreak = 1
        while(currentNum in A):
            currentStreak += 1
            currentNum -= 1
        currentNum = A[i] + 1
        while(currentNum in A):
            currentStreak += 1
            currentNum += 1
        longestStreak = max(longestStreak, currentStreak)
    return longestStreak

Explanation:

For each element in A, linearly search for consecutive elements greater and lesser than the current element. Keep a track of the current streak and the longest streak of consecutive elements in the array.

• Time Complexity: O(n³): The inner loops linearly search for consecutive elements. This search will be done as long as the streak will be and the longest a streak can be is n. Thus, inside the outer loop, the worst-case time complexity is O(n²). Also, this process is repeated for each element of the array. So time Complexity = n * O(n²) = O(n³)
• Space Complexity: O(1)

Using sorting:

def longestConsecutiveSequence(A: List[int], n: int) -> int:
    longestStreak = 0
    A.sort()
    i = 0
    while i < n:
        currentStreak = 1
        while(i < n and A[i + 1] == A[i] + 1):
            currentStreak += 1
            i += 1
        if currentStreak == 1:
            i += 1
        longestStreak = max(longestStreak, currentStreak)
    return longestStreak

Explanation:

Sort the entire array A. Now, the consecutive elements will be linearly lined up next to each other. Linearly check for the longest consecutive sequence now.

• Time Complexity: Sorting an array + Linear Traversal of the array = O(nlogn) + O(n) = O(nlogn)
• Space Complexity: O(1)

Using hash table:

def longestConsecutiveSequence(A: List[int], n: int) -> int:
    longestStreak = 0
    hash = {i for i in A}
    for i in range (n):
        if A[i] - 1 not in hash:
            currentStreak = 1
            currentNum = A[i] + 1
            while currentNum in hash:
                currentStreak += 1
                currentNum += 1
            longestStreak = max(longestStreak, currentStreak)
    return longestStreak

Explanation:

We can improve the time complexity of searching consecutive elements by using a hash table which can check the presence of consecutive elements in O(1) average.

• Time Complexity: O(n) The time complexity of the search operation is now O(1), we can see that each element is searched at most two times, i.e. first, in the if condition, and second, in the while loop condition. So the complexity due to this is linear ( O(n) ) in nature. Since each element is visited only once, Time Complexity: O(n)
• Space Complexity: O(n), for the Hash Table

That’s it!

If you are interested in solving more problems, do follow me and join me on this journey.

See you tomorrow!

Cheers!