LCS: Why is my count variable not performing erroneously

Question

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

The problem lies with list(set(...)), which doesn't guarantee an ordered list. — Swifty
– Swifty, Commented Nov 4, 2022 at 18:41
what can be then done to ensure a sorted list from the set in O(n) time? — mkj4332
– mkj4332, Commented Nov 4, 2022 at 18:44
There are ways to sort in O(n) time, under specific conditions: stackoverflow.com/questions/63561965/… ; but I bet it's possible to do what is expected without sorting. I'll let you do some research. — Swifty
– Swifty, Commented Nov 4, 2022 at 19:05

Swifty · Accepted Answer · 2022-11-04 20:03:14Z

1

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

edited Nov 4, 2022 at 20:03

answered Nov 4, 2022 at 19:15

Swifty

3,4642 gold badges6 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

vim1729 · Accepted Answer · 2022-11-04 20:11:34Z

1

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

answered Nov 4, 2022 at 20:11

vim1729

567 bronze badges

1 Comment

Swifty Over a year ago

Nice solution, probably more efficient than mine.

Collectives™ on Stack Overflow

LCS: Why is my count variable not performing erroneously

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related