Longest Common Subsequence

Longest Common Subsequence

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

Input: nums = [0,3,7,2,5,8,4,6,0,1]

Output: 9

Approach 1:

While this question would be easy if the array was sorted, it is not and sorting will take O(N log n) time, exceeding the requirement.

The best way for these type of array questions is to utilize different data structures.

Since we only need to return the longest subsequence, we do not need to care about any duplicates, making hash set very useful for this question.

I would try to find the minimum value in within the subsequence, and try to update the current streak and the longest streak by iterating through the list.

Implementation:

class Solution:


    def longestConsecutive(self, nums: List[int]) -> int:
        result = 0
        no_dup = set(nums)
        for num in no_dup:
            if num - 1 not in no_dup:
                current_num = num
                current_streak = 1
                while current_num + 1 in no_dup:
                    current_num += 1
                    current_streak += 1
                result = max(result, current_streak)
        return result
        

Complexity Analysis:

Time Complexity: O(n)

Space Complexity: O(n)

Reflection

I feel like I have underestimated myself too easily these days. Remember what I have been through, what I have accomplish, and what if.

Let’s treat all these questions as questions that will be on the interview, and I would have to write out the answers for each and every one of them.

내가 내 자신을 믿자!