Longest Consecutive Sequence

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We are given an unsorted array of integers.
  • We need to find the length of the longest consecutive sequence of numbers in the array.
  • A consecutive sequence is defined as a sequence of numbers where each number appears exactly once and the difference between consecutive numbers is exactly 1.

2. Analyze the problem: To solve this problem, we can use a hash set to efficiently check for the presence of numbers in the array. By iterating through each element of the array and checking for consecutive numbers, we can find the longest consecutive sequence.

3. Design an algorithm: Here is the algorithm to solve the problem:

  1. Initialize an empty hash set.
  2. Insert all the numbers from the array into the hash set.
  3. Initialize a variable longest_sequence to 0 to keep track of the length of the longest consecutive sequence.
  4. Iterate through each element num in the array:
    • If num-1 is not in the hash set, this means num is the start of a new consecutive sequence.
    • Count the length of the consecutive sequence by incrementing current_sequence while num+1 is in the hash set.
    • Update longest_sequence if the current sequence is longer than the previous longest sequence.
  5. Return longest_sequence.

4. Explain your approach: The approach involves using a hash set to efficiently check for the presence of numbers in the array. We iterate through each element of the array and check if the element is the start of a new consecutive sequence. If it is, we count the length of the consecutive sequence by incrementing a counter while the next number is present in the hash set. We update the length of the longest consecutive sequence if the current sequence is longer.

5. Write clean and readable code:

python
def longestConsecutive(nums):
    num_set = set(nums)
    longest_sequence = 0

    for num in nums:
        if num - 1 not in num_set:
            current_sequence = 1
            while num + 1 in num_set:
                num += 1
                current_sequence += 1
            longest_sequence = max(longest_sequence, current_sequence)

    return longest_sequence

6. Test your code: Let's test the code with different test cases to ensure its correctness:

  1. Test case with an empty array:

    • Input: nums = []
    • Expected output: 0

  2. Test case with a single element in the array:

    • Input: nums = [5]
    • Expected output: 1

  3. Test case with multiple elements in the array:

    • Input: nums = [100, 4, 200, 1, 3, 2]
    • Expected output: 4 (as the longest consecutive sequence is [1, 2, 3, 4])
python
# Test case 1: Empty array
nums = []
print(longestConsecutive(nums))  # Output: 0

# Test case 2: Single element
nums = [5]
print(longestConsecutive(nums))  # Output: 1

# Test case 3: Multiple elements
nums = [100, 4, 200, 1, 3, 2]
print(longestConsecutive(nums))  # Output: 4

7. Optimize if necessary: The current solution has a time complexity of O(n), where n is the length of the array. We iterate through each element of the array once. The space complexity is also O(n) as we store the numbers in a hash set. This solution is already efficient and does not require further optimization.

8. Handle error cases: The code handles the case where the input array is empty. It returns 0 as the output in that case.

9. Discuss complexity analysis: The time complexity of the solution is O(n), where n is the length of the array. We iterate through each element of the array once. The space complexity is also O(n) as we store the numbers in a hash set. The solution has a linear time complexity and linear space complexity.

Next Post Previous Post