Lexicographically Smallest Subsequence of Size K (LC 1673: Find the Most Competitive Subsequence)

Problem Statement

Given an array nums and an integer k, return the most competitive subsequence of length k. A subsequence A is more competitive than B if at the first differing index, A has a smaller value.

Example 1:

Input:  nums = [3, 5, 2, 6], k = 2
Output: [2, 6]
Explanation: Among subsequences of length 2: [3,5],[3,2],[3,6],[5,2],[5,6],[2,6]. The smallest is [2,6].

Example 2:

Input:  nums = [2, 4, 3, 3, 5, 4, 9, 6], k = 4
Output: [2, 3, 3, 4]

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 1 <= k <= nums.length

Difficulty: Medium

---

Pattern Recognition

• Input structure: 1D array.
• What are we optimizing? lex-smallest subsequence of a fixed size.
• Pattern: monotonic stack (a Google favorite).
• Why: lex order compares left-to-right. To make the result small, you want small values as early as possible. A monotonic non-decreasing stack lets you pop larger values when a smaller one arrives — but you must be careful not to pop so many that you can't fill k slots.

---

Approach

Brute Force

Enumerate all C(n, k) subsequences and pick the smallest. O(n choose k), infeasible.

Optimal — Monotonic Stack with Budget

Key Insight: Use a stack. For each incoming nums[i], pop while all of these hold:

• Stack is non-empty.
• Top of stack > nums[i].
• You have enough remaining elements (n - i) to still fill k: formally stack.size + (n - i) > k.

After scanning, the stack may be larger than k (rare but possible for sorted descending inputs — actually never for this problem because the invariant guarantees size ≤ k at the end). Trim to size k from the right.

stack = []
n = len(nums)
for i in 0..n-1:
    while stack and stack.top() > nums[i] and len(stack) + (n - i) > k:
        stack.pop()
    if len(stack) < k:
        stack.push(nums[i])
return stack

The len(stack) < k guard keeps the stack from overflowing. Combined with the stack.size + (n - i) > k pop condition, you end with exactly k elements.

Time: O(n) amortized — each element pushed and popped at most once. Space: O(k) for the stack.

---

Walkthrough

nums = [2, 4, 3, 3, 5, 4, 9, 6], k = 4.

i	nums[i]	Stack before	Pop?	Push?	Stack after
0	2	[]	—	yes (size<k)	[2]
1	4	[2]	2>4? no	yes	[2, 4]
2	3	[2, 4]	4>3 AND size(2)+remaining(6)=8>4 → pop	yes	[2, 3]
3	3	[2, 3]	3>3? no	yes	[2, 3, 3]
4	5	[2,3,3]	3>5? no	yes	[2, 3, 3, 5]
5	4	[2,3,3,5]	5>4 AND size(4)+remaining(3)=7>4 → pop	yes	[2, 3, 3, 4]
6	9	[2,3,3,4]	4>9? no	size=4 ≮ k, skip	[2, 3, 3, 4]
7	6	[2,3,3,4]	4>6? no	size=4 ≮ k, skip	[2, 3, 3, 4]

Return [2, 3, 3, 4].

---

Implementation

TypeScript

function mostCompetitive(nums: number[], k: number): number[] {
    const stack: number[] = [];
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        // Pop while top is larger AND we can still reach size k
        while (
            stack.length > 0 &&
            stack[stack.length - 1] > nums[i] &&
            stack.length + (n - i) > k
        ) {
            stack.pop();
        }
        if (stack.length < k) stack.push(nums[i]);
    }
    return stack;
}

C++

vector<int> mostCompetitive(vector<int>& nums, int k) {
    vector<int> stk;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && stk.back() > nums[i] &&
               (int)stk.size() + (n - i) > k) {
            stk.pop_back();
        }
        if ((int)stk.size() < k) stk.push_back(nums[i]);
    }
    return stk;
}

Watch out:

1. Forgetting the stack.size + (n - i) > k guard pops too aggressively and leaves the result shorter than k.
2. Using >= in stk.back() > nums[i] changes behavior on duplicates — here you want strict > to avoid popping and re-pushing equal values.
3. Forgetting the < k push guard bloats the stack past the target size.

---

Complexity Analysis

	Time	Space
Brute Force	O(C(n, k) * k)	O(k)
Monotonic Stack	O(n)	O(k)

Bottleneck: each element is pushed once and popped at most once, so total work is linear.

---

Edge Cases

1. k = n — answer is nums unchanged; the pop guard prevents any removal.
2. k = 1 — answer is [min(nums)]; stack continuously replaces its single element.
3. Already sorted ascending — no pops; take first k elements.
4. Sorted descending — every step pops as much as allowed; end with the last k elements.
5. All equal values — no pops (strict > guard); take first k.
6. Very large array (n = 10^5) — O(n) handles it; avoid recursion.

---

Related Problems

• LC 402 — Remove K Digits — Same monotonic stack with budget; output is a string of size n - k.
• LC 316 / 1081 — Remove Duplicate Letters (smallest in lex order) — Monotonic stack with a "last-occurrence" guard.
• LC 321 — Create Maximum Number — Two-array version of this trick, picking from two sources.
• LC 503 — Next Greater Element II — Monotonic stack on a circular array.

---

What Is Expected at Each Level

Junior: Likely needs a prompt to see the stack. With help, implements the loop but may forget the size + remaining > k guard.

Mid-level: Writes the full invariant correctly, explains why the guard is needed, tests on descending / ascending edge cases.

Senior (L4 target): Immediately recognizes the monotonic-stack-with-budget family (LC 402, 316, 321), writes the solution in one pass, and can articulate the invariant formally. Comments on amortized O(n) via potential argument.