C++ O(1) Extra Space O(nlogn) Time Solution.


  • 0
    F

    To achieve O(1) extra space, the key is to build the heap in the profits array.

    class Solution {
        void quicksort(vector<int> & master, vector<int> & slave, int l, int h)
        {
            if (l >= h)
                return;
            swap(master[h - 1], master[(h + l)/2]);
            swap(slave[h - 1], slave[(h + l)/2]);
            int pivot = master[h - 1];
            int j = l;
            for (int i = l; i < h - 1; ++ i)
            {
                if(pivot > master[i])
                {
                    swap(master[i], master[j]);
                    swap(slave[i], slave[j]);
                    j ++;
                }
            }
            swap(master[h - 1], master[j]);
            swap(slave[h - 1], slave[j]);
            quicksort(master, slave, l, j);
            quicksort(master, slave, j + 1, h);
        }
    public:
        int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
            quicksort(capital, profits, 0, capital.size());
            int i = 0, j = 0;
            while(k > 0)
            {
                if (w < capital[i] || i >= capital.size())
                {
                    if (j <= 0)
                        return w;
                    pop_heap(profits.begin(), profits.begin() + j);
                    w += profits[j - 1];
                    k -- ;
                    j --;
                    continue;
                }
                profits[j] = profits[i]; 
                push_heap(profits.begin(), profits.begin() + j + 1);
                ++ i;
                ++ j;
            }
            return w;
        }
    };
    

Log in to reply
 

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