algoadvance

Leetcode 128. Longest Consecutive Sequence

Problem Statement

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 complexity.

Clarifying Questions

1. Input Constraints:
   • Can nums contain duplicate elements?
   • What is the range of values for elements in nums?
2. Output:
   • What should be returned if nums is an empty array?

Assumptions

1. nums can contain both positive and negative integers.
2. An empty array should return 0 as there are no consecutive sequences.

Strategy

To achieve the O(n) time complexity:

1. Using a Hash Set:
   • Insert all elements into a hash set. This allows for O(1) average-time complexity checks for the presence of elements.
2. Check for Starting Points:
   • Iterate through each element in the list. For each element, check if it is the start of a sequence by checking if element-1 does not exist in the set.
   • If it is the start of a sequence, expand the sequence by continuously checking the existence of the next element (element + k) in the set.
3. Track the Longest Sequence:
   • Keep track of the maximum length of consecutive sequences found.

Code

Here’s the C++ code that implements this strategy:

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;

        unordered_set<int> numSet(nums.begin(), nums.end());
        int longestStreak = 0;

        for (int num : nums) {
            // Check if it's the start of a sequence
            if (!numSet.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                // Check the length of the current streak
                while (numSet.count(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }

                longestStreak = max(longestStreak, currentStreak);
            }
        }
        
        return longestStreak;
    }
};

Time Complexity

• Time Complexity: O(n)
  • Creating the hash set takes O(n) time.
  • The while loop inside the for loop will run at most n times total across all iterations because each element is checked only once.
• Space Complexity: O(n)
  • Because we’re storing all elements in a hash set, the space complexity is also O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?