# Removing the largest values encountered so far in a list

The problem is, in summary:

A set of values will be given. Whenever the input is -1, the largest number from the values inputted until then needs to be printed, and is then deleted.

Here is the code that I wrote for it:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int main()
{
int val;
int N, M, x=0, i=0;
vector<int> visits;
cin>>N>>M;
for(x=0; x<N+M; x++)
{
cin>>val;
visits.push_back(val);
if(val==-1)
{

cout<<*max_element(visits.begin(), visits.end())<<endl;
i++;
visits.erase(max_element(visits.begin(), visits.end()));
}
}

return 0;
}


The program gives correct answers, but it exceeds the time limit for some of the test cases. The test data isn't given, so I don't know for what size of test data it fails. Is there some other way by which I can optimize my code?

-
Use a std::set rather than a std::vector. The data is kept ordered so finding the largest item is easy (its at set.begin()). Also removing an element from a set is O(1) while removing an element from a vector is O(n). Note inserting into a vector is O(1) while inserting into a set is O(ln(n)) – Loki Astari Sep 2 '14 at 15:07
Alternatively convert your vector into a heap. std::make_heap() then adding an element is O(ln(n)) with std::push_heap() and removing the largest element is O(ln(n)) with std::pop_heap(). – Loki Astari Sep 2 '14 at 15:10
@LokiAstari: Some nit picks: Set is ordered from low to high (see this). Removing from a set is amortized constant time (but the examples could be carefully crafted to make it log time). Inserting into a vector is linear time on average, appending is constant time, same is true for erasing (linear on average, constant at the end). – Nobody Sep 2 '14 at 15:45
Set by default is ordered low to high. ideone.com/cKXcWw not that hard to change though. User is inserting at end of vector so O(1) insertion. But erasing from random location so O(n) on erase. – Loki Astari Sep 2 '14 at 18:06
You could avoid calling max_element by storing the largest value in a separate variable (and in the vector) and on every insertion, check if the new value is larger than the current maximum. If so, change the variable, if not only insert it in the vector. After deleting you would need one call to max_element though, to find the new maximum. – 11684 Sep 2 '14 at 21:36

## You are using a C++ compiler!

So you should also use its features:

• don't declare all variables up front but as late as possible
• don't using namespace std; that only gives you trouble later on
• you don't need to return 0; at the end of main

## Formatting

Your formatting can be improved. You should use more spaces especially around (binary) operators, this makes it easier to parse (or rather tokenize) the code with your eye.

## Naming

You have nearly only single letter names which is bad. The fact that two of them look like macro names does not make it better. Consider:

• N -> populationHeadCount
• M -> executionCount
• val -> currentVisitorWealth
• visits -> stillLivingWealthiest

## Unused variable

The variable i is initialized and incremented but never read.

## Inserting "the king"

Your code unconditionally inserts the wealth val even if it is the king (-1), thus introducing even more entries in visits.

## Speed up

Reading rules more closely than you have given them here yields:

You may assume that no two citizens have the same wealth.

Which makes this problem a perfect fit for an std::set (as mentioned by Loki):

#include <iostream>
#include <set>
#include <algorithm>

int main() {
int populationHeadCount, expectedExecutionCount;
std::cin >> populationHeadCount >> expectedExecutionCount;
std::set<int> stillLivingWealthiest;
int executionNumber = 0;
while (executionNumber < expectedExecutionCount) {
int currentVisitorWealth;
std::cin >> currentVisitorWealth;
if (currentVisitorWealth == -1) {
std::cout << *--stillLivingWealthiest.end() << std::endl;
stillLivingWealthiest.erase(--stillLivingWealthiest.end());
++executionNumber;
} else {
stillLivingWealthiest.insert(currentVisitorWealth);
}
}
}


Explanation: A std::set stores the elements sorted from minimum to maximum, so we only need to look at the end to get and delete the maximal element.

-
Optimize the for loop. You can stop reading when the king has made all his appearances for the day. No point in continuing to read and insert if the king is not going to show up. – Loki Astari Sep 2 '14 at 15:28
@LokiAstari: Changed. Why didn't you post a good answer instead of these comments? I would have given you an upvote. – Nobody Sep 2 '14 at 15:31
Because I have nothing major to add. All the important points have all bee covered. And writing an answer takes effort while comments are quick. – Loki Astari Sep 2 '14 at 15:36
Thanks for the suggestion on naming variables. But how can using namespace std cause trouble? Also, I had read on some online forum that it is "good practice" to use the return statement at the end of the main. So, should i use it or not? – user283779 Sep 2 '14 at 18:16
@user283779: Take a look at stackoverflow.com/q/1452721/760746 for detailed explanations of this issue. – Nobody Sep 2 '14 at 19:42

Part of the problem is that you call max_element() twice.

If there are to be n elements in a list, of which d maxima are to be deleted, a naïve std::vector solution would take O(d n), with the time being dominated by searching for the maxima and re-compacting the vector after deletion.

Therefore, you need a better data structure. Typically, the problem of repeatedly finding and removing the maximum value would be solved by using a max heap. In C++, the heap is the basis of std::priority_queue. With a heap/priority queue, finding and removing the maxima d times can be done in O(d log n) time. The solution would then be dominated by the time to insert n entries, which is O(n log n).

Assuming that d is a significant proportion of n, the heap-based solution should perform better.

-
From my understanding of heaps removing of d maxima would take $O(d~ \log n)$ time. – Nobody Sep 2 '14 at 15:28
@Nobody Thanks! I stand corrected. The conclusion is the same, though. – 200_success Sep 2 '14 at 15:36

This is what I would write:

#include <iostream>
#include <set>
#include <algorithm>

int main()
{
// Experimenting with new ways to read a stream.
std::istream_iterator<int>  loop(std::cin);

// Allows me to declare and initialize variable in the same line.
int populationHeadCount     = *loop++;
int expectedExecutionCount  = *loop++;

// Use a set with order greatest to least.
// This makes identifying an removing the largest value easy (its at begin())
std::set<int, std::greater<int>> stillLivingWealthiest;

// Keep going while we have executions to do.
// No point in interviewing more people after that.
while (expectedExecutionCount > 0)
{
int currentVisitorWealth    = *loop++;

if (currentVisitorWealth == -1)
{
std::cout << *stillLivingWealthiest.begin() << "\n";
stillLivingWealthiest.erase(stillLivingWealthiest.begin());
--expectedExecutionCount;
}
else
{
stillLivingWealthiest.insert(currentVisitorWealth);
}
}
}

-
I thought about using istream_iterator as well but I find they look a bit odd outside of algorithms. Using expectedExecutionCount to count down I would rename it to remainingNumberOfExecutions (or remainingExecutionCount or remainingKingVisits). Inverting the sort order of the set makes retrieving the maximum nicer. Finally, I noticed that (regardless of which ordering you use for set) the requirement to remove the maximum from the set undermines the random access assumption of the amortized constant time for deletion. – Nobody Sep 3 '14 at 10:45

As this is Code Review, I will start with the code presented:

1. Calling max_element twice hurts the execution time.
2. Using unsorted vector hurts the execution time the most.
3. Use sync_with_stdio to spead up reading and writing.
4. The king is not to be inserted in the container.
5. Format the code and name the values that we know, what they are.
That could even help you realize, what are the values good for.

I would use heap (std::priority_queue) on top of pre-allocated vector to get best performance (if there is no problem with the pre-allocation, the number of heads looks like to be exactly for this). I am not sure if the heap can get empty, another check to exit the loop could be needed in such case.

#include <iostream>
#include <vector>
#include <queue>

int main() {
//  this can speed up reading
std::cin.sync_with_stdio(false);
//  get the numbers
int heads, count;
std::cin >> heads >> count;
//  and setup the heap (with pre-allocation)
std::vector<int> buffer;
buffer.reserve(heads);
std::priority_queue<int> heap(
std::less<int>(), std::move(buffer));
//  the big loop
while (count) {
int wealth;
std::cin >> wealth;
if (wealth >= 0) {
heap.push(wealth); continue; }
//  execution
std::cout << heap.top() << '\n';
heap.pop(); --count;
}
}


EDIT: The code has been corrected on two places according to comments below:

    std::priority_queue<int> heap(
std::less<int>(), std::move(buffer));  // std::move here


And:

        std::cout << heap.top() << '\n';       // '\n' instead of std::endl here

-
Never seen a priority queue constructed like that. Nice that they updated the interface. BUT. It does NOT look like your reserve will affect the priority queue, because you are copying an empty array into the queue. You should probably use the move constructor. std::priority_queue<int> heap(std::less<int>(), std::move(buffer));. Since you especially took note of sync_with_stdio() you should also probably not use std::endl as the flush makes this very inefficient. Replace with '\n' to get the same affect. Overall very nice +1 – Loki Astari Sep 4 '14 at 7:34
@LokiAstari: You are correct, the intent was good, but the code is not that perfect. I will think about updating it later, when I have more time to. – firda Sep 4 '14 at 10:29
You should create an own function for the buffer allocation to avoid introducing an unused variable (buffer) into the scope. Putting several commands on one line can be a readability issue (they might be overlooked) and using continue instead of else can make the code less readable. – Nobody Sep 4 '14 at 15:00
@Nobody: 1. The buffer is not unused but rather short-lived, and could probably be made disapear earlier, that is the part I may agree with. 2. That continue can be made on separate line as well as that --count, but I don't like complex if-if-else-if-if-else-else when you can cut it with break or continue. I am a single programmer managing many projects, that is for sure influencing my code-style. – firda Sep 4 '14 at 15:12

One thing you could use is Boost Container flat_set. The first answer to this question tells you a little about them.

Another thing you could do, if you want to stick with std::vector, is insert values always in the correct position, so you will have the max_element always in last, or first position.

For that you could use std::lower_bound and vector::insert.

-