RANGES - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest

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

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