~/leetcode$cat128. Longest-Consecutive-Sequence

Last problem in the Array/Hashing section…

The brute force method would just be to go through all elements and start a sequence from that element and keep track of the maximum length. This would take O(n^2) time worst case (consider the input [5, 4, 3, 2, 1])

So from the brute force method, there is an important realisation: we don’t need to start a sequence from an element x if the element x - 1 is in the list (which we can check in O(1) time if we convert the list into a hashset first.

With this optimisation, we go through each element at most twice (once when we consider it for as a start of a sequence and once as part of a sequence - we can guarantee this second case only happens once as we consider each sequence max once).

For example:

Input [5, 4, 3, 2, 1]

Brute force:

• check 5 - 5
• check 4 - 4, 5
• check 3 - 3, 4, 5
• check 2 - 2, 3, 4, 5
• check 1 - 1, 2, 3, 4, 5 (longest length 5)
• checks 15 numbers

Optimised:

• check 5 - 5 - 1 exists (skip)
• check 4 - 4 - 1 exists (skip)
• check 3 - 3 - 1 exists (skip)
• check 2 - 2 - 1 exists (skip)
• check 1 - 1 - 1 does not exist - 1, 2, 3, 4, 5 (longest length 5)
• checks 10 numbers

Note: this problem took longer than I thought since there was one test case that was TLE… the solution was to change the object I was iterating through in the for loop (for (int num: nums) to for (int num: numsSet))… So why is it faster looping through a set compared to an array, I have no idea… If I had to guess maybe it’s because the array is a reference to an array outside of the function (and the set is in this function?) - not sure…

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int longest = 0;
        unordered_set<int> numsSet(nums.begin(), nums.end());

        for (int num: numsSet) {
            if (numsSet.contains(num - 1)) {
                continue;
            }

            // start sequence
            int length = 0;
            while (numsSet.contains(num + length)) {
                ++length;
            }

            longest = max(longest, length);
        }

        return longest;
    }
} 

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 10m 15s