# RANGES - Editorial

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

EASY

STACK

# PROBLEM:

Given an integer array of size N. Find the lexicographically smallest subsequence of length K.

# QUICK EXPLANATION:

Keep a mono increasing stack as result. If the current element `a` is smaller than the last element in the stack, we can replace it to get a smaller sequence.

# EXPLANATION:

Find all the subsequences of length K with recursion by making the choice of picking or not picking an element. The total number of subsequences that will be produced will be 2^N. Find the lexicographically smallest among all these subsequences by comparing them.

The array has N elements but we need a subsequence of length K hence we need to remove N-K elements such that the remaining K elements make the lexicographically smallest subsequence.

Suppose in our current answer subsequence the last element is X, now if an element comes with a value less than X and we still haven’t removed N-K elements then we can remove the X and keep that new element in the answer. The stack will be the perfect choice for the problem as we will be removing the elements in a LIFO manner but the array can also be used as shown in the solution.

Therefore the algorithm will be:

• Traverse the array from left to right. Kepp removing the top element from `ans` if the current element is smaller than the top element and we haven’t removed the N-K elements.
• Push the current element into the `ans`
• If there are still elements left to be removed then remove the required number of top elements from `ans`.

# COMPLEXITIES

Here N is the size of the array.

TIme Complexity:
O(N).
We are just traversing the array from left to right and all stack operations are O(1).

Space Complexity:
O(N)
The worst case will be when the array is sorted in ascending order in that case all elements will be stored in the `ans` and will be removed in the end.

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;

vector<int> solve(vector<int>& nums, int k) {

int i,n = nums.size(), removed = n-k;

vector<int> ans;

for(i=0;i<n;i++)
{
while(ans.empty()==0 && nums[i]<ans.back() && removed>0)
{
removed--;
ans.pop_back();
}

ans.push_back(nums[i]);
}

while(removed--)
ans.pop_back();

return ans;
}

int main() {
ios_base::sync_with_stdio(false);

int t,n,k,i,x;

cin>>t;

while(t--)
{
cin>>n>>k;
vector<int> v;

for(i=0;i<n;i++)
{
cin>>x;
v.push_back(x);
}

vector<int> ans = solve(v, k);

for(i=0;i<k;i++)
cout<<ans[i]<<" ";

cout<<endl;
}

return 0;
}
``````