Original problem · C++ solution
A max-heap provides the same largest two values as sorting on every iteration.
A max-heap provides the same largest two values as sorting on every iteration. If the second largest is zero, at most one positive value remains; otherwise decrement both, reinsert them, and count the operation.
- Time: O((N+sum A) log N).
- Extra space: O(N).
A default priority_queue exposes the largest value through top(). Save that value before pop(), and reinsert updated values to restore the ordering.
Check the second-largest value before decreasing it; zero marks the stopping condition.
State the invariant without looking at the code. Give one input that breaks the most tempting incorrect approach, then add it to the tests.