842. The Most Competitive Pick of Length k
Read n values and an integer k. Choose exactly k of them, keeping their original order, so
that the chosen sequence is the SMALLEST possible when compared position by position: compare the
first entries, and only if they are equal compare the second, and so on.
Print the k chosen values on one line, separated by single spaces.
n = 4, k = 2, values 3 5 2 6 -> 2 6
n = 5, k = 3, values 2 4 3 3 5 -> 2 3 3
n = 5, k = 1, values 4 2 9 1 3 -> 1
In the second row the greedy instinct is to start 2 then 3 then 3, and that is right, but
notice that the second 3 is kept only because dropping it would leave too few values behind.
## Why this is not just sorting, and not just a minimum
The order cannot be changed, so the answer is a subsequence, and picking the k smallest values
ignores the order entirely. The first chosen value must be the smallest value that still leaves
k - 1 values after it, and then the problem repeats on the rest.
## The stack, and the room check that makes it work
Walk left to right holding the chosen prefix on a stack, kept NON-DECREASING from the bottom up because we are minimising and want the small values early.
while the stack is non-empty
and the top is > a[i]
and (stack size - 1) + (values remaining from i) >= k:
pop
if the stack size is still below k:
push a[i]
The pop is the exchange argument again: replacing a larger value with a smaller one at an earlier position improves the sequence at the first place they differ, and nothing before that position changes.
## The condition that has no counterpart in problem 841
(stack size - 1) + (n - i) is how many values would remain available if this pop happened. If
that drops below k the pop is illegal, because the answer could no longer be filled to length
k. Problem 841 has no such check, since it deletes a fixed COUNT rather than keeping a fixed
LENGTH, and it can always fall back on truncating the tail.
Leave the check out and 2 1 2 1 2 1 2 1 2 1 with k = 5 comes back too short, because the ones
happily pop everything and then there is nothing left to fill with.
## Why the push is also guarded
Once the stack already holds k values and no pop is legal, the arriving value cannot help: any
later position is worse than the position it would have to take. So it is skipped, not pushed and
truncated later.
## The comparison that decides ties
The pop test is top > a[i], strictly. With >= an equal value would replace an equal value for
no gain and spend room that the length check needs; 1 1 1 1 1 1 with k = 3 is the case that
exposes it.
## Related problems
Problem 841 maximises by deleting a fixed count and pops on the opposite comparison, and problem 172 minimises by deleting a fixed count. Reading all three together is the fastest way to see that the stack direction follows the objective, not the problem.
## Sizes and widths
Values reach 10^9 and the answers are input values, printed unchanged. Nothing is summed or
multiplied, so 32 bits is enough.
## Cost
Time O(n): every value is pushed at most once and popped at most once. Space O(k).
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-10^9 ≤ a[i] ≤ 10^9`
Input
The first line contains two integers n and k.
The second line contains n integers a[0] ... a[n-1].
Output
Print k integers on one line, separated by single spaces: the smallest subsequence of length k, in the order the values appear in the input. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.