Longest Consecutive Sequence
In this tutorial, we are going to solve a leetcode problem, Longest Consecutive Sequence in python.
Task:
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:
if nums == []:
return 0
nums = list(set(nums))
nums.sort()
cur, streak = 1, 1
for i in range(1,len(nums)):
if nums[i] == nums[i-1] + 1:
cur += 1
else:
streak = max(streak, cur)
cur = 1
streak = max(streak, cur)
return streak
Steps:
step1: In this problem, first we are going to check if num is empty if it is we return the length as 0.
step2: Now, we make the num unique list and sorted it.
step3: Now we created 2 other variables cur and streak which will hold the streak of longest length and cur holds the number of elements in a particular iteration.
step4: Now we loop into the num from index 1, and check is num[I] == num[i-1]+1 to check if the current element is 1+ of the previous one.
step5: if it is then we increment cur otherwise, we update the streak and or assign the cur = 1 as the previous streak is over.
step6: After the for loop we return the streak as our answer.
