Is my solution O(n) time/space? With linked list.


  • 0
    V

    I create Sequence elements telling the FIRST and LAST element of the sequence, sorting them in a linked list.

    For each input number:

    • scroll the sequence list as far as the input is LESS than next sequence (or end of list) (while).
    • check if the input is in the current sequence (continue)
    • if extends both, merge
    • else if extends one, update bound
    • else there's no extension at all, so add new sequence (one element)

    In the meanwhile:
    At every sequence change update maxSeqLength

    class Solution {
    
       struct Sequence {
            int first;
            int last;
            Sequence* next;
            
            Sequence(int aFirst, int aLast) 
            : first(aFirst), last(aLast), next(NULL) {}
            
            ~Sequence() { if (next) delete next; }
        };
    
        public:
            int longestConsecutive(vector<int> &num) {
                int maxSeqLength = 0;
                vector<int>::iterator it = num.begin();
                int minInt = std::numeric_limits<int>::min();
                Sequence dummyHead(minInt,minInt); 
                
        
                while(it != num.end())
                {
                    Sequence* head = &dummyHead;
                    int val = *it++;
         
                                            // Scroll list when val > next_sequence_first 
                    while (head->next && (val > head->next->first))
                    {
                        head = head->next;
                    }
                                            // Skip if already contained in next or previous sequence
                    if ((head->next && val == head->next->first) || (val <= head->last) )
                    {
                        continue;
                    }            
                                            // Check if expands previous sequence (high bound) or next sequence (low bound)
                    bool bExpandPrevious = (head->last  == val - 1 );
                    bool bExpandNext = (head->next && (head->next->first == val + 1));
                    
                                            // it can happen we've got a value that merges two sequences 
                    if (bExpandPrevious && bExpandNext)
                    {
                                               //Merge
                        Sequence* pTemp = head->next;
                        head->next = head->next->next;
                        head->last = pTemp->last;
                        pTemp->next = NULL;
                        
                        delete pTemp;
                        maxSeqLength = std::max(maxSeqLength, head->last - head->first + 1);
                    }      
                    else if (bExpandPrevious)    // or expands previous only
                    {
                                                //Update last
                         head->last = val;
                         maxSeqLength = std::max(maxSeqLength, head->last - head->first + 1);
                    }       
                    else if (bExpandNext)       // or expands last only
                    {
                                                 // Update first
                        head->next->first = val;
                        maxSeqLength = std::max(maxSeqLength, head->next->last - head->next->first + 1);
                    }
                    else                        // or it's a brand new sequence (of 1 element!)                     
                    {
                        // insert in between
                        Sequence* pTemp = head->next;
                        head->next = new Sequence(val, val);
                        head->next->next = pTemp;
                        maxSeqLength = std::max(maxSeqLength, head->next->last - head->next->first + 1);
                    }
                 }
                return maxSeqLength;
            }
        };

  • 0
    L

    You used two linked lists to represent the first and last element in sequence, so every time you meet a new element, you need to go through the two lists, which is O(n). So actually, your algorithm is o(n^2). You should use Hash map to speed it up. The search operation of hash is only O(1), so your algorithm will be O(n).


  • 0
    V

    I think I am actually using one list with two values per node (low and high of a sequence).
    For each new element I go through the one list to update the list itself and the maxSequenceLength counter. Where does it look like two lists?


Log in to reply
 

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