Solution: Find the Most Competitive Subsequence
Tags: algorithms, java, javascript, python
Published: 2021-02-22 01:30:17

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/find-the-most-competitive-subsequence/discuss/1027592).*

---

#### [Leetcode Problem #1673 (*Medium*): Find the Most Competitive Subsequence](https://leetcode.com/problems/find-the-most-competitive-subsequence/)

---

#### ***Description:***
</br>
(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given an integer array `nums` and a positive integer `k`, return the most __competitive__ subsequence of `nums` of size `k`.
>
An array's subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.
>
We define that a subsequence `a` is more competitive than a subsequence `b` (of the same length) if in the first position where `a` and `b` differ, subsequence `a` has a number less than the corresponding number in `b`. For example, `[1,3,4]` is more competitive than `[1,3,5]` because the first position they differ is at the final number, and `4` is less than `5`.

---

#### ***Examples:***

>
Example 1:||
|---:|---|
Input:|nums = [3,5,2,6], k = 2
Output:|[2,6]
Explanation:|Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.
>
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`

---

#### ***Idea:***
</br>
(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The problem's definition for "competitiveness" sounds just like a standard sort order, and just like a standard sort order, it can be improved by removing any larger number that comes before a lower number. Also, the further left in the input you make this removal, the larger its impact.

The trick here is to perform this operation as many times as you can while still making sure you have at least **K** elements left.

The standard solution here will resemble a **stack**, as we'll iterate through our input (**N**) and push values to the answer stack. If the next value (**N[i]**) is lower than the top value of the stack, then we'll pop numbers off the stack until it's not. By doing this, our stack will always be sorted in ascending order.

If at any point the number of elements you can safely remove (**moves**) is reduced to **0**, then we combine our stack with the remaining elements of **N** and **return**. If we reach the end of **N** and our stack is longer than **K**, just return the first **K** elements.

But as is often the case when we're doing a one-time pass through an array and selectively removing elements, we can increase our efficiency by doing an **in-place stack** using a **2-pointer system** by using the early positions of **N** as our answer stack.

---

#### ***Implementation:***

Python, unlike the other three languages, actually prefers the normal stack solution rather than an in-place version.

C++ can drastically improve the speed up its solution of this particular problem via use of a custom lambda function designed to speed up I/O.

---

#### ***Javascript Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var mostCompetitive = function(N, K) {
    let len = N.length, moves = len - K
    for (let i = 0, j = 1; j < len;) {
        while (N[j] < N[i] && moves) i--, moves--
        if (!moves) return N.slice(0,i+1).concat(N.slice(j))
        N[++i] = N[j++]
    }
    return N.slice(0,K)
};
```

---

#### ***Python Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def mostCompetitive(self, N: List[int], K: int) -> List[int]:
        i, moves = 0, len(N) - K
        ans = []
        for x in N:
            while ans and moves and x < ans[-1]:
                ans.pop()
                moves -= 1
            ans.append(x)
        return ans[:K]
```

---

#### ***Java Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int[] mostCompetitive(int[] N, int K) {
        int len = N.length;
        int moves = len - K;
        for (int i = 0, j = 1; j < len;) {
            while (moves > 0 && i >= 0 && N[j] < N[i]) {
                i--;
                moves--;
            }
            N[++i] = N[j++];
        }
        return Arrays.copyOfRange(N,0,K);
    }
}
```

---

#### ***C++ Code:***
</br>
(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    vector<int> mostCompetitive(vector<int>& N, int K) {
        int len = N.size();
        int moves = len - K;
        for (int i = 0, j = 1; j < len;) {
            while (moves && i >= 0 && N[j] < N[i])
                i--, moves--;
            N[++i] = N[j++];
        }
        return vector<int>(N.begin(), N.begin() + K);
    }
};

static int fastIO = [] {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
```