LeetCode #128: Longest Consecutive Sequence

LeetCode Solutions

https://leetcode.com/problems/longest-consecutive-sequence/

To solve this problem, we can first sort the input array. Then, we can iterate through the sorted array and check if the current number is equal to the previous number plus one. If it is, we can increment a counter variable. Otherwise, we can reset the counter variable to 1. We also keep track of the maximum counter value seen so far, which represents the length of the longest consecutive sequence.

Steps to solve the problem:

  1. Create a function called “longestConsecutive” that takes an array of integers as input.
  2. If the input array is empty, return 0.
  3. Sort the input array in ascending order using the sort() method.
  4. Create a variable called “max_len” and set it to 1.
  5. Create a variable called “curr_len” and set it to 1.
  6. Iterate through the sorted array using a for loop. For each number in the array:
  7. If the current number is equal to the previous number plus one, increment the “curr_len” variable.
  8. Otherwise, reset the “curr_len” variable to 1.
  9. If the “curr_len” variable is greater than the “max_len” variable, update the “max_len” variable.
  10. Return the “max_len” variable.

Python Code: Here’s the Python code to solve the Longest Consecutive Sequence problem:

class Solution:
    def longestConsecutive(self, nums):
        if not nums:
            return 0
        nums.sort()
        max_len = 1
        curr_len = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1] + 1:
                curr_len += 1
            elif nums[i] != nums[i-1]:
                curr_len = 1
            max_len = max(max_len, curr_len)
        return max_len

Time and Space Complexity:

The time complexity of this solution is O(n log n), where n is the length of the input array. This is because we need to sort the input array, which takes O(n log n) time. The for loop that follows takes O(n) time.

The space complexity of this solution is O(1), as we are using constant extra space to store the counter variables and the maximum length seen so far.