LeetCode — Find the Most Competitive Subsequence

Problem Link: https://leetcode.com/problems/find-the-most-competitive-subsequence/

Photo by Derzulya Zaza on Unsplash

Problem Description: 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

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.

Approach Used: Stack

Explanation: Instead of finding the elements to be added, our approach will find the elements to be removed. For this, we will remove the biggest number found so far whenever we encounter a number smaller than it. We will keep doing it until we have removed the number of elements we wanted to remove (number_of_elements_in_array-k). To do this in linear time, the best approach is to use a stack. There can be cases where the whole array is sorted in increasing order so while traversing the array, we will keep inserting elements in the stack. So to ensure that our answer size doesn’t exceed k, we will remove elements from the stack until we reach the target. Finally, we will transfer the output of stack in an array and that’ll be our answer.

Code: (Java)

public int[] mostCompetitiveUsingStack(int[] nums, int k){
   int elements_to_be_removed = nums.length-k;
   Stack<Integer> answerStack = new Stack<>();
   int[] ans = new int[k];
   for (int num : nums) {
      while (!answerStack.empty() && answerStack.peek() > num && elements_to_be_removed-- > 0)
                    answerStack.pop();
                
       answerStack.push(num);
       }
   while(!answerStack.empty() && elements_to_be_removed-->0)
       answerStack.pop();
   for(int i=k-1; i>=0; i--)
       ans[i] = answerStack.pop();
   return ans;
   }
 public int[] mostCompetitive(int[] nums, int k) {
    return mostCompetitiveUsingStack(nums, k);
 }

Complexity:
Space Complexity: O(N). If all elements are in increasing order then all the elements will be inserted in the stack.
Time Complexity: O(N). The whole array will be traversed once.
Here N is the length of the array.

The Github link contains code with comments for a better explanation.
Github Link:
https://github.com/siddhaant-jain/LeetCode/blob/master/DailyChallenge/src/CodeFiles/FindTheMostCompetitiveSubsequence.java

Note: I was attempting to solve this problem using dynamic programming considering it a special case of ‘Longest Increasing Subsequence’ problem. I understood the approach from the below mentioned youtube link and then wrote the code myself:
https://www.youtube.com/watch?v=1nbb_RhqpdY&t=273s