[Problem proposal] (Lexicographically smallest after removing at most k elements from list)

[guoyiz23]

Problem name: Lexicographically smallest post-removal

Problem

Given a list $a$ of integers, return the lexigraphically smallest list after removing at most $K$ elements.

Constraint

• $10^9 \leq a_i \leq 10^9$

Solution / Reference

Based on https://atcoder.jp/contests/abc262/editorial/4531

template <typename T> 
vector<T> lexicographically_smallest_post_remove(const vector<T>& a, int num_to_remove) {
    vector<T> res;
    if (num_to_remove >= int(a.size())) return res;
    auto expected_sz{int(a.size()) - num_to_remove};
    for (auto i{0}; i < int(a.size()); i++) {
        while (num_to_remove > 0 && !res.empty() && res.back() > a[i]) {
            res.pop_back();
            num_to_remove--;
        }
        if (int(res.size()) < expected_sz) {
            res.push_back(a[i]);
        }
    }

    return res;
};

Note

There may already be an item that tests this but it is not straightforward to find. Thus, I thought that on the site, one could add keywords for each of the items in the "Problem List" and a corresponding search feature. A keyword for this item would be "lexicographic".

[maspypy]

Thank you for suggesting the problem.
Regarding the problem title, I think something like "lexicographically smallest subsequence" would sound more natural.

As for the search tags, we currently have no plans to implement them.