CODEWITHSUNDEEP
pythonsetsequence
user24982840
user24982840

Reputation: 9

Time Complexity For "Longest Consecutive Sequence" Leetcode problem solution

SO I had question regarding the time complexity for my solution for the LeetCode problem "Longest Consecutive Sequence". In this problem, we're given an unsorted array of integers, and need to find the length of the longest sequence of integers with consecutive values that all appear in the array.

For example, if the array is [100,4,200,1,3,2], then the desired result is 4, because integers 1 through 4 all appear in the array.

The problem specifies to solve this in O(n) time.

So my solution uses the python set. I first add all the elements in the list to the set and then iterate through the list, checking if n-1 exists in the set to check for the beginning of a sequence and then once I have the beginning of a sequence I keep checking for n+1 in the set until I can't find it anymore(while keeping track of the length of the sequence).

My question is on the time complexity of my solution. I'm confused on whether the worst case time complexity of this would be n2 or 3n. An example input for the worst case would be nums = [5,4,3,2,1]. If I'm iterating through the list finding the first element in a sequence and then making a sequence out of that, would I not have O(n) for iterating through the list and then another O(n) for making a sequence going backwards from 1,2,3,4,5?

Upvotes: 0

Views: 182

Answers (1)

ruakh
ruakh

Reputation: 183514

The solution you presented is in fact in O(n). Nice work!

You are correct that your solution uses O(n) time and then O(n) time again in the case you mention; but that's fine, because O(n) + O(n) is O(n), because the whole point of big-O notation is to ignore constant factors.

Edit: A commenter writes:

In the his solution, for each item, he is looping through other items (which is what my solution does too). That is a multiplication not an addition and in the worst case likely O(n(n-1)).

— but that's not correct. Because you have logic "checking if n-1 exists in the set to check for the beginning of a sequence", you only enter the inner loop once for each consecutive sequence; and for each sequence, the inner loop has only k iterations, where k is the number of numbers in that sequence, so the total number of iterations of the inner loop (across all sequences) is Σk = n. So the total cost is in O(n), assuming that Python set insertions and lookups are both O(1).

Upvotes: 0

Related Questions