13 ms(95.95%) + 19 ms(75.44%) C++ solution + explanation


  • 0
    L

    22ms solution, beats 71.58%, O(n) run-time + O(n) extra space.

    Slam all those integers into a hash set.
    Then use the hash set to check if sequences exist via. "while (mySet.find(nums[i]++) != mySet.end()) {length++;}" line.

    The line "if (mySet.find(nums[i]-1) != mySet.end()) {continue;}" allows us to only look for numbers that begin a sequence.
    Effectively eliminating the need to check a sequence unless its actually the beginning of one. This line alone is the reason why its O(n) run-time.

    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            unordered_set<int> mySet(nums.begin(), nums.end());
            int result = 0;
            
            for (int i=0; i<nums.size(); i++)
            {
                if (mySet.find(nums[i]-1) != mySet.end()) //don't compare if the element is not the beginning of a sequence.
                {
                    continue;
                }
                int length = 0;
                while (mySet.find(nums[i]++) != mySet.end()) //we found an element that could be a beginning of a sequence, now loop thru the hash set for a sequence.
                {
                    length++;
                }
                result = max (result, length);
            }
            return result;
        }
    };
    

    13 ms solution, beats 95.95%, O(nlogn) run-time and O(1) extra space.

    For some reason this one is faster, not sure what happened here. Also, probably one of the first solutions that should come to mind.

    Basically sort the array, then go thru the array once counting for sequences. Very simple and straight forward.

    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            if (nums.size() == 0){
                return 0;
            }
            
            sort(nums.begin(), nums.end());
            int consecutiveCompare = nums[0]-1;
            int counter = 0;
            int longestCounter = 0;
            
            for (int i=0; i<nums.size(); i++){
                if (consecutiveCompare == nums[i]) { //handle duplicates
                    continue;
                }
                else if (consecutiveCompare+1 != nums[i]){ //found the end of a sequence, now reset the sequence
                    consecutiveCompare = nums[i];
                    longestCounter = max(longestCounter, counter);
                    counter = 1;
                }
                else { //found an element of a sequence, now continue to the next element.
                    consecutiveCompare = nums[i];
                    counter++;
                }
            }
            
            longestCounter = max(longestCounter, counter);
            
            return longestCounter;
        }
    };
    

  • 0
    C

    Thanks for the easy solution.
    However, I think the first solution could be O(n^2) in the worst case, e.g. [1, 2, 3.... n].


  • 0
    L

    @Chienlima said in 13 ms(95.95%) + 19 ms(75.44%) C++ solution + explanation:

    Thanks for the easy solution.
    However, I think the first solution could be O(n^2) in the worst case, e.g. [1, 2, 3.... n].

    The first solution cannot be n^2.
    I mentioned that the line "if (mySet.find(nums[i]-1) != mySet.end()){continue;}" makes this O(n).
    If you do this manually you will see why. Let me try to explain in a bit detail.

    Say you had 1 to 10 in sorted order like you stated.
    Make a hash set first. O(n).
    Go thru the array once. The first element happens to start a sequence, so lets check it. It goes thru 1 to 10 so its O(n).
    After we got the sequence, next we move on to the second element but its not the start of a sequence so we continue to the third, forth, etc... , another 1 to 10 O(n).

    O(n) + O(n) + O(n)
    So in total its 3O(n), effectively O(n) run-time.
    We are not starting a sequence search for every element in the array, only the ones that are the beginning of one, which is the most important part to make this O(n) run-time.
    Yes it may seem like O(n^2) run-time at first by looking at the code, but you will soon see, at most each element in the array can only be checked twice. Once to check if its a beginning of a sequence and once for whether its part of a sequence .
    It also important to note, even if you have a better big O, that does not necessarily mean its faster. It will depend on what data is being passed thru and its size.

    Hope that helps.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.