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:
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.
Input: nums = [2,4,3,3,5,4,9,6], k = 4 Output: [2,3,3,4]
Approach: If you look closely, this problem is actually finding the k minimum elements in the given sequence. Basically if we find the first minimum element at say index i then next element will be the MIN (nums[i + 1] ... nums[n - 1]) and so on. Of course we need to take care of the fact that if we are choosing nums[i] as first element then Count(nums[i + 1] ... nums[n - 1]) >= k - 1, otherwise we won't get k elements. Here is our simple algorithm to solve this problem:
- minIndex = -1
- WHILE k > 0
- currMin = int.Max
- FOR i = minIndex + 1 to i + k <= n // To force to have k elements
- IF currMin > nums[i]
- currMin = nums[i]
- minIndex = i
- result.Add(currMin)
- k = k - 1
- RETURN result
This approach will solve the problem but the time complexity of this approach is O(k * n) which is expensive. Let's see how we can reduce it. If you look closely we are processing the same elements multiple times. Take an example here:
[2, 3, 5, 4]
In first pass, after doing every comparison, the first minimum element we will find is 2 at index = 0. Now if you see we again need to comparison from index = 1.... n- k. What if we would have stored these comparison somewhere so that we would know that next element will be 3 in first pass itself?
We can use stack here to store these comparisons. With stack, our algorithm will look like:
- Stack stack
- FOR i = 0 To n
- IF stack.Count < k AND (stack.Count == 0 || stack.Top <= nums[i])
- stack.Push(nums[i])
- ELSE IF stack.Count > 0 AND stack.Top > nums[i]
- WHILE stack.Count > 0 AND stack.Count + n - i > k AND stack.Top > nums[i]
- stack.Pop()
- stack.Push(nums[i])
- FOR i = k - 1 To 0
- result[i] = stack.Pop();
- RETURN result
This solution will solve our problem in linear time and it is the most optimal solution I know in terms of time.
We are taking extra space here in the form of stack. We can use our result array itself to represent stack to reduce extra space. You can understand it by just looking at the implementation.
Implementation in C#:
With Stack:
public int[] MostCompetitiveWithStack(int[] nums, int k)
{
if (nums?.Length < k)
{
return null;
}
int[] result = new int[k];
Stack<int> stack = new Stack<int>();
for (int i = 0; i < nums.Length; ++i)
{
if (stack.Count < k && (stack.Count == 0 || stack.Peek() <= nums[i]))
{
stack.Push(nums[i]);
}
else if (stack.Count > 0 && stack.Peek() > nums[i])
{
while (stack.Count > 0 && stack.Count + nums.Length - i > k && stack.Peek() > nums[i])
{
stack.Pop();
}
stack.Push(nums[i]);
}
}
for (int i = k - 1; i >= 0; --i)
{
result[i] = stack.Pop();
}
return result;
}
WithoutStack:
public int[] MostCompetitive(int[] nums, int k)
{
if (nums?.Length < k)
{
return null;
}
int[] result = new int[k];
result[0] = nums[0];
int resultIndex = 0;
for (int i = 1; i < nums.Length; ++i)
{
if (resultIndex < k - 1 && result[resultIndex] <= nums[i])
{
result[++resultIndex] = nums[i];
}
else if (resultIndex >= 0 && result[resultIndex] > nums[i])
{
while(resultIndex >= 0 && resultIndex + 1 + nums.Length - i > k && result[resultIndex] > nums[i])
{
result[resultIndex--] = int.MinValue;
}
result[++resultIndex] = nums[i];
}
}
return result;
}
Complexity: O(n)
No comments:
Post a Comment