LCS: Why is my count variable not performing erroneously-CodePudding

LeetCode: longest consecutive sequence

Question: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

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

nums = [0,3,7,2,5,8,4,6,0,1]
nums = list(set(nums)) # O(n) operation 
res = 0
count = 1

if len(nums)==1: # edge case
    res = 1

    
for i in range(len(nums)-1):
    if abs(nums[i] - nums[i 1]) == 1:
        count =1 
        print(count)
    else:
        res = max(res, count) 
        count = 1
    
print(res)```

this prints as follows (print(count)) adds an unneccessary 
2
3
4
5
6
7
8
9
0

And when input is nums = [100,4,200,1,3,2]
Output is for print(count):
2
3
3

Count variable is misbehaving

CodePudding user response：

This one should work efficiently enough (for each element,the set is accessed about 3 times so, including the creation of the set, that would make the complexity O(4n), which is still O(n)):

def longest_seq(a: list) -> int :
    a = set(a)
    max_seq = 0
    for i in a:
        if i-1 in a:
            continue
        else:
            j= i 1
            while j in a:
                j  = 1
            max_seq = max(max_seq, j-i)
    return max_seq

CodePudding user response：

You could also do something like this, without using sets. Just create an array of zeros and assign the values of the given array variables as one and calculate the max_seq.

def longest_seq(a: list) -> int :
    bit = [0 for i in range(max(a) 2)]
    for i in a: 
        bit[i] = 1
    max_seq = count = 1
    for i in range(1,len(bit)):
        if bit[i] == bit[i-1] == 1:
            count =1
        else:
            max_seq = max(max_seq, count)
            count = 1
    return max_seq
print(longest_seq([5,4,7,8,1,2,3,4,9,10,11,12,13])) # ans = 7