The Blind 75 Leetcode Series: Longest Consecutive Sequence

Today, we are working on 128. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

It’s a short description. We have a list of integers, and we want to check what’s the longest consecutive sequence we can find. A group of numbers are considered a sequence if the next number is 1 + the previous number. We can shuffle the list in order to find the longest sequence.

So, couple things to specify:

  1. Are we expecting empty list? Do we simply return 0 or do we deal with it as a special case?
  2. For repeating numbers, do we always only count them once? (i.e. 0, 0, 1, 2 count as a sequence of 3)

If the answers are yes and yes, then we can start.

Since the characteristic of a sequence involves checking if the next number is 1 + the previous, it’s natural to rearrange the numbers so that they are in ascending order. That way we can be sure that previous number is smaller than the next.

Then we have to deal with repeating numbers. We only need to keep 1 appearance of an element, so using a set to get rid of extra could be a good idea.

Once we have a list of unique numbers, we just need to iterate through it and check if the next number is 1 + current number while tracking the current longest sequence count. When we meet a gap (a number that’s not 1 +), we reset the current longest sequence count to 1 and compare current longest sequence with the max sequence and get the new max.

To put everything together, we have

def longestConsecutive(nums):
if not nums:
return 0
nums = list(set(nums))
nums.sort()
max_consecutive = 1
current_consecutive = 1
for idx in range(1, len(nums)):
if nums[idx] == nums[idx-1] + 1:
current_consecutive += 1
else:
max_consecutive = max(max_consecutive, current_consecutive)
current_consecutive = 1
max_consecutive = max(max_consecutive, current_consecutive)
return max_consecutive

What’s the time complexity?

Turning a list into a set takes O(N). Turning a set into a list also takes O(N). The sorting in python is an O(N log N) operation. Then we have the for loop that loops through the list, which is also O(N). Therefore, we have O(N + N + N log N + N) => O(N log N) as our overall time complexity.

def longestConsecutive(nums):
if not nums:
return 0
nums = list(set(nums)) # O(N) for list -> set then for set -> list
nums.sort() # O(N logN)
max_consecutive = 1
current_consecutive = 1
for idx in range(1, len(nums)): # O(N)
if nums[idx] == nums[idx-1] + 1:
current_consecutive += 1
else:
max_consecutive = max(max_consecutive, current_consecutive)
current_consecutive = 1
max_consecutive = max(max_consecutive, current_consecutive)
return max_consecutive

This solution passes the leetcode test cases, but the question actually wants us to do it in O(N).

This mean sorting is out of option. We need to find another way to look up the numbers. We still need to go through the numbers, and for each number we need a way to look up for n -1 and n + 1 and so on. Our best bet is using a hashset where lookup time is O(1), fitting our need.

We first feed the list into the hashset, effectively taking out the duplicates. Then we take a number in the list, knowing it must exists (as we just took it), set the current_consecutive to 1.

We then first go down (decrement) by 1 and check if such number exists in the hashset. If it does, we add current_consecutive by 1. Then we go down by 1 more and repeat the process.

Once we no longer see the number in the hashset, we go back to the original number. This time we increment by 1 and check if the value exists.

In order to make sure we don’t repeat the same sequence, we remove the number found from the hashset (so that next time when we see the number when looping through the list, we do not repeat the process.) Without doing it, we increase our time complexity since we are doing repeating work.

Once we’ve gone both direction and found that there’s no longer any number fitting our criteria, we compare the current_consecutive with our max_consecutive, originally set to 1.

To put everything in code:

def longestConsecutive(nums):
if not nums:
return 0
s = set(nums)
max_consecutive = 1
# for each number, we go two directions
for num in nums:
count = 1
current_consecutive = 1
# go down and look in hashset, remove such number if found
while num - count in s:
s.remove(num - count)
current_consecutive += 1
count += 1
# reset count so we can start over
count = 1
# go up and look in hashset, remove such number if found
while num + count in s:
s.remove(num + count)
current_consecutive += 1
count += 1
max_consecutive = max(max_consecutive, current_consecutive)
return max_consecutive

We have successfully reduced our time complexity to linear time, O(N). Transforming the list to a set is O(N). The for-loop is another O(N), and the 2 while-loops combined gives us O(N). HOWEVER, because we are removing elements, every time we visit a number, we delete it, so the set gets smaller and smaller as we go.

def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
s = set(nums) # O(N)
max_consecutive = 1
for num in nums: # O(N)
count = 1
current_consecutive = 1
while num - count in s: # Combined with .remove, we visit each number in the hashset at most once. So even though this while loop resides inside a for loop, we actually only take linear time.
s.remove(num - count)
current_consecutive += 1
count += 1

count = 1

while num + count in s: # similar to above comment, with .remove, we visit each number at most once.
s.remove(num + count)
current_consecutive += 1
count += 1
max_consecutive = max(max_consecutive, current_consecutive)
return max_consecutive

What’s important about this approach is to understand that we are only taking linear time. The interviewers WILL ask you to explain why this is linear and not O(N²). Prepare to explain thoroughly.

Other than that, just remember how you find the next number and make sure you’re tracking the current and max consecutive sequence. Then you should be good to go.

That’s it! Another problem down.

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jonathan Chao

Jonathan Chao

I am a software developer who has been in this industry for close to a decade. I share my experience to people who are or want to get into the industry