# PROBLEM LINK:

* Author:* Sumukh Bhardwaj

*Rahul Sharma*

**Tester:***Sumukh Bhardwaj*

**Editorialist:**# DIFFICULTY:

EASY

# PREREQUISITES:

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:

**Subtask #1:**

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.

**Subtask #2:**

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

For all subtasks to pass

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;
}
```