Longest Consecutive Sequence in Python

Suppose we have an array of integers. We have to find the length of the longest consecutive elements sequence. So if the input is like [100, 4, 250, 1, 3, 2], answer will be 4, as the longest consecutive sequence is [1,2,3,4].

To solve this, we will follow these steps −

• make the array set, longest := 0

• for i in range array −

  • if i – 1 is not in a −

    • current := i, streak := 0

    • while i in a −

      • increase i by 1, increase streak by 1

      • longest := max of longest and streak

• return longest

Example

Let us see the following implementation to get a better understanding −

 Live Demo

class Solution(object):    def longestConsecutive(self, a):       a = set(a)       longest = 0       for i in a:          if i-1 not in a:             current = i             streak = 0             while i in a:                i+=1                streak+=1                longest = max(longest,streak)       return longest ob = Solution() print(ob.longestConsecutive([100,4,250,1,3,2]))

Input

[100,4,250,1,3,2]

Output

4