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

• 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;
}
};
``````

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