The logic :
Input the total number of items n
and then read n
strings.
Since only the last appearance of any item matters (because re-opening pushes it to the top), iterate the input array in reverse.
Use a set<string>
to keep track of already-included items.
If an item hasn't been inserted yet, add it to the result vector and mark it in the set.
Finally, print the ans
vector which stores the final order of items, from top to bottom.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<string> arr(n);
cin.ignore();
for(int i = 0;i<n;i++){
getline(cin, arr[i],'\n');
}
vector<string> ans;
set<string> s;
for(int i = n-1;i>=0;i--){
if (!s.count(arr[i])){
ans.push_back(arr[i]);
s.insert(arr[i]);
}
}
for(int i = 0 ; i < ans.size();i++){
cout << ans[i] << endl;
}
return 0;
}
Time Complexity:
O(n)
— iterating through the list once in reverse.
O(log k)
per set
operation, where k
is number of unique strings, but effectively O(1)
average due to small input limits.
Space Complexity:
O(k)
— for storing unique items in a set
and final output in ans
.
The key insight is to efficiently count elements smaller than each array element in two ranges:
lower_bound()
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> arr(n);
for(int i = 0 ; i < n;i++){
cin >> arr[i];
}
multiset<int> s;
int k;
cin >> k;
vector<int> left(n,0),right(n,0);
for (int i = 0; i < n; ++i) {
left[i] = distance(s.begin(), s.lower_bound(arr[i]));
s.insert(arr[i]);
}
s.clear();
for (int i = n - 1; i >= 0; --i) {
right[i] = distance(s.begin(), s.lower_bound(arr[i]));
s.insert(arr[i]);
}
int cnt = 0;
for (int i = k; i < n-k; ++i) {
cout << arr[i] << endl;
cout << left[i] << " " << right[i] << endl;
if (left[i] >= k && right[i] >= k)
cnt++;
}
cout << cnt << endl;
}
O(n log n) - Two passes through array with multiset insert and lower_bound operations
O(n) - For multiset, left array, right array, and input storage