O(1) space and O(n) time using doubly linked list in C++


  • 0
    int thirdMax(vector<int>& nums) {
            list<int> l;
            
            for(auto i = nums.begin(); i != nums.end(); i++){
                list<int>::iterator ins_pos;
                
                ins_pos = l.begin();
                // calculate the position to insert
                while(ins_pos != l.end() && *ins_pos > *i){
                    ins_pos++;
                }
                // don't insert if element is repeated
                if(ins_pos == l.end() || *ins_pos != *i){
                    l.insert(ins_pos, *i);
                }
                // pop minimum element if list size increases beyond 3
                if(l.size() > 3){
                    l.pop_back();
                }
            }
             // check if at least three different values exist in list
            if(l.size() == 3){
                return l.back();
            }else{
                return l.front();
            }
        }
    

Log in to reply
 

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