Sponsored
Sponsored
This approach uses a stack to build the competitive subsequence. The basic idea is to iterate through the array and maintain a stack where the final size is k. For each element, we decide whether it should be added to the stack or replace the top element of the stack, which ensures the stack remains a competitive sequence.
We will replace the top element of the stack if the current element is smaller and there are enough elements left to fill the required subsequence size.
This method ensures that the maintained sequence is minimal and competitive, based on the problem constraints.
Time Complexity: O(n) where n is the number of elements in nums.
Space Complexity: O(k) to store the competitive subsequence.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] MostCompetitive(int[] nums, int k) {
6 Stack<int> stack = new Stack<int>();
7 int to_remove = nums.Length - k;
8
9 foreach (var num in nums) {
10 while (stack.Count > 0 && stack.Peek() > num && to_remove > 0) {
11 stack.Pop();
12 to_remove--;
13 }
14 stack.Push(num);
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) {
result[i] = stack.Pop();
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {3, 5, 2, 6};
int[] result = sol.MostCompetitive(nums, 2);
Console.WriteLine(string.Join(" ", result));
}
}The C# solution uses the Stack class to ensure the competitive subsequence is built correctly. After building the stack, it extracts the final result array of size k.
This approach builds upon the idea that maintaining a competitive subsequence can be achieved by iteratively reducing and replacing elements in a greedy fashion, focusing directly on modifications to an output array.
This strategy is slightly different from a pure stack-based approach as it directly handles result index placement while keeping track of candidates for subsequences and managing the required number of subsequence slots.
Time Complexity: O(n).
Space Complexity: O(k).
public class Solution {
public int[] FindMostCompetitive(int[] nums, int k) {
int[] result = new int[k];
int j = 0;
for (int i = 0; i < nums.Length; i++) {
while (j > 0 && result[j - 1] > nums[i] && j + nums.Length - i > k) {
j--;
}
if (j < k) {
result[j] = nums[i];
j++;
}
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {2, 4, 3, 3, 5, 4, 9, 6};
var result = sol.FindMostCompetitive(nums, 4);
Console.WriteLine(string.Join(", ", result));
}
}The C# implementation leverages direct array manipulation to find the competitive subsequence, ensuring that logic and iterations strictly manage placement based on selection criteria.