Leaders from the Right
National Olympiad — Regional round (2016 season)
Submission name: leaders.cpp
Problem summary
A leader is an element at least as large as every value to its right. Print all leader values in their input order.
Input
n followed by n integers.
Output
The leader values.
Constraints
0 < n < 1000000; values lie in [−10^9,10^9].
Worked example
Input and output for the worked example discussed below.
Input
7 50 1 40 2 3 4 30
Output
50 40 30
Solution analysis
- Scan right to left while remembering the largest already-seen value. This maximum describes precisely the elements strictly to the current position’s right.
- Retain the current value when it is at least that maximum, then update the maximum. Equal suffix maxima are all leaders. Initialize below the permitted value range so negative arrays work.
- The sample discovers30,40,50 in that order. Reverse the discovery list to print50 40 30. The last element always qualifies because there are no later elements.
Why it works
The maintained suffix maximum makes the comparison exactly equivalent to the leader definition at each position. All positions are tested, and reversal restores the original order without changing membership.
Complexity: O(n) time and O(n) space for the array and result.
Watch out. Use ≥, not >. Handle all-negative arrays and reverse the backward discovery order.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>values(n);
for(int&value:values){
cin>>value;
}
int maximum=numeric_limits<int>::min();
vector<int>leaders;
for(int i=n-1;i>=0;i--){
// Equal suffix maxima also satisfy the definition.
if(values[i]>=maximum){
leaders.push_back(values[i]);
maximum=values[i];
}
}
reverse(leaders.begin(),leaders.end());
for(size_t i=0;i<leaders.size();i++){
if(i>0){
cout<<' ';
}
cout<<leaders[i];
}
cout<<'\n';
}