C++ O(nlogn)

The given parameters are meant to misguide you! my initial (not the optimal) solution was to use the given vector, sort it, erase the two elements in front, insert a new element according to the 1:2 given weight ratio. However, this is not the optimal solution:

• the erase() method traverses the vector lineraly every time in order to erase the correct element, which is O(n) complexity.
• the insert() requires manual search for the correct placement, which is O(n).
• using push_back() instead of insert() requires sort() after each iteration which is O(nlogn)
• solving the question using the vectors is correct however not optimal as it is solved in O(n^2) complexity.

the correct and optimal method to solve this question is to use a MinHeap (aka a priority queue with a std::greater comperator).

• creating the heap from the vector is done by make_heap() (aka Heapify) algorithm which is O(n).
• using heap gives you direct access to the top() element which is the only relevant element in each iteration, in constant time O(1).
• heap automatically sorts itself with swifting up/down every time a new element is pushed/poped, in O(logn).
• considering the loop, the overall complexity of the code is O(nlogn).

heres my version of the code:

int cookies(int k, vector<int> A) {
    if(A.empty())
        return -1;
    
     priority_queue<int, std::vector<int>, std::greater<int> > heap(A.begin(),A.end(), std::greater<int>()); // min heap
		 
     int iterations = 0, c1, c2;
     
     while(heap.top() < k && heap.size() >= 2){
         c1 = heap.top();
         heap.pop();
         
         c2 = heap.top();
         heap.pop();
        
         heap.push(c1 + 2*c2);
         iterations++;
     }
     
     return (heap.top() < k) ? -1 : iterations;
}