Day 8: Longest Consecutive Sequence - leetcode - Python3

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 <= 105
• -109 <= nums[i] <= 109

SOLUTION:

class Solution:

    def longestConsecutive(self, nums: List[int]) -> int:

        num_set: set[int]=set(nums)

        longest_Seq: int=0

        for i in nums:

        #check if preceding element exist

            if i-1 not in num_set:

                current_seq: int=0

                while i+1 in num_set:

                    current_seq +=1

                    i+=1

                longest_Seq= max(current_seq, longest_Seq)

        return longest_Seq

Time Complexity: O(n)

• The code iterates through each element in the nums list once, resulting in a linear time complexity relative to the size of the input.
• The operations performed within the loop, such as checking element existence in the set and incrementing values, have constant time complexity.
• Overall, the time complexity is dominated by the loop iteration, resulting in a linear time complexity of O(n).
• 
  

Space Complexity: O(n)

• The space complexity is determined by the additional memory used to store the set num_set.
• In the worst case, where all elements in nums are unique, the set num_set would contain all elements of nums.
• Therefore, the space complexity is proportional to the size of the input, resulting in O(n) space complexity.

How it works:

1. num_set: set[int] = set(nums): Creates a set num_set containing unique elements from the input nums list.
2. longest_Seq: int = 0: Initializes the variable longest_Seq with the value 0, which will store the length of the longest consecutive sequence found.
3. for i in nums:: Iterates over each element i in the nums list.
4. if i - 1 not in num_set:: Checks if the preceding element of i does not exist in the num_set. If so, it means i is the start of a consecutive sequence.
5. current_seq: int = 0: Initializes the variable current_seq with the value 0, which will store the length of the current consecutive sequence.
6. while i + 1 in num_set:: Enters a loop that continues as long as the next consecutive element of i exists in the num_set.
7. current_seq += 1: Increments the current_seq by 1 to track the length of the consecutive sequence.
8. i += 1: Increments the value of i by 1 to move to the next consecutive element in the sequence.
9. longest_Seq = max(current_seq, longest_Seq): Updates the value of longest_Seq with the maximum value between current_seq and longest_Seq, ensuring it holds the length of the longest consecutive sequence encountered so far.
10. return longest_Seq: Returns the value of longest_Seq as the result of the method.