Intuition
As we have to regularly maintain the sorted array and have to pick the top two largest elements from it. The direction in which our mind first goes is towards the Priority queue. The idea here is to use a max priority queue. We will first insert all the elements in the priority queue. Then we will keep performing the following operations till the size of the queue becomes 1 or 0:
- Take two elements at the top of the queue. Pop them.
- If they are not equal, then we will insert their absolute difference. Else, we will continue.
Now, if the size of the queue is 0, we will print ‘-1’. Else if its size is one, then we will print that single element present in the queue.
Things will become much clearer from the code.
Code
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Function to reduce the array and print the remaining element.
int reduceArray(vector<int> &arr)
{
priority_queue<int> maxPq;
// Inserting elements of array in priority_queue.
for (int i = 0; i < arr.size(); i++)
maxPq.push(arr[i]);
// Looping through elements.
while (maxPq.size() > 1)
{
// Remove largest element.
int maxEle = maxPq.top();
maxPq.pop();
// Remove 2nd largest element.
int secondMaxEle = maxPq.top();
maxPq.pop();
// If these are not equal.
if (maxEle != secondMaxEle)
{
// Pushing into queue.
maxPq.push((maxEle - secondMaxEle));
}
}
// If only one element is there in the heap.
if (maxPq.size() == 1)
cout << maxPq.top();
else
cout << "-1";
}
int main()
{
// Taking user input.
int n;
cin >> n;
vector<int> arr(n, 0);
for (int i = 0; i < n; i++)
cin >> arr[i];
// Calling function 'reduceArray()'.
reduceArray(arr);
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Input
4
1 2 3 4
Output
-1
Complexity Analysis
Time Complexity
O(N * log N), where ‘N’ is the length of the array.
As we are inserting ‘N’ elements in the priority queue and each insertion costs us O(log N) time thus ‘N’ insertions will cost O(N * log N). After insertion we are just looping through all the elements in the queue that will cost us O(N) time. Thus the overall complexity is O(N) + O(N * log N) ~ O(N * log N).
Space Complexity
O(N), where ‘N’ is the length of the array.
As we are using a priority queue to store the elements in the queue and as there are ‘N’ elements, extra space of O(N) will be required.
Frequently Asked Questions
What is a Priority Queue?
This is the implementation of the heap in which the root element is a higher priority in the form of maximum or minimum.
How do we declare min heap in c++?
priority_queue< data_type, vector<data_type>, greater<data_type>> variable_name

You can also try this code with Online C++ Compiler
Run Code
Write applications of Priority Queue.
Application of priority queue are as follows:-
1. Some algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc
2. CPU scheduling in the operating system.
3. Sorting algorithm like heap-sort.
Conclusion
We saw how we could solve the problem, ‘the last element remaining by deleting the two largest elements and replacing them with their absolute difference if they are unequal’ with the help of a priority queue. We first inserted all the elements in the queue and then, according to the question popped the top two elements.
Recommended Reading:
For more such interesting questions, move over to our industry-leading practice platform Coding Ninjas Studio to practice top problems and many more.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Till then, Happy Coding!