Jobs

Interviews

Discussions

Find the Most Competitive Subsequence

Medium

Uber

1 view

Topics:

ArraysGreedy AlgorithmsStacks

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.

For example:

nums = [3, 5, 2, 6], k = 2. The most competitive subsequence is [2, 6].
nums = [2, 4, 3, 3, 5, 4, 9, 6], k = 4. The most competitive subsequence is [2, 3, 3, 4].

Can you implement a function to find the most competitive subsequence?

Find the Most Competitive Subsequence

Medium

Uber

1 view

Topics:

ArraysGreedy AlgorithmsStacks

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.

For example:

nums = [3, 5, 2, 6], k = 2. The most competitive subsequence is [2, 6].
nums = [2, 4, 3, 3, 5, 4, 9, 6], k = 4. The most competitive subsequence is [2, 3, 3, 4].

Can you implement a function to find the most competitive subsequence?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Can k be zero or larger than the size of the input array?
If multiple subsequences of length k are equally competitive, is any one acceptable?
Can the input array contain duplicate numbers, and if so, how should they be handled when comparing subsequences?
What should I return if the input array is null or empty, or if k is invalid?

Brute Force Solution

Approach

The brute force approach is like trying every single possible combination to find the best one. We essentially go through all the subsequences and pick the 'most competitive' one based on the problem's definition.

Here's how the algorithm would work step-by-step:

Consider every possible subsequence that could be created from the original sequence.
This means trying every possible combination of including or excluding each number in the original sequence.
For each subsequence, check if its length is what we are looking for.
If the subsequence length is not what we want, ignore it and move on to the next subsequence.
If the subsequence length is correct, compare it to all other subsequences of the correct length that we've seen so far.
Determine which subsequence is 'more competitive' by comparing them element by element until one is found to be better than the other.
Keep track of the 'most competitive' subsequence we've found so far.
After looking at all possible subsequences, return the 'most competitive' one we found.

Code Implementation

def find_most_competitive_subsequence_brute_force(numbers, subsequence_length):
    most_competitive_subsequence = []

    # Generate all possible subsequences
    for i in range(1 << len(numbers)):
        current_subsequence = []
        for j in range(len(numbers)):
            if (i >> j) & 1:
                current_subsequence.append(numbers[j])

        # Only consider subsequences of correct length
        if len(current_subsequence) == subsequence_length:

            # First subsequence of correct length initializes
            if not most_competitive_subsequence:
                most_competitive_subsequence = current_subsequence

            else:
                # Compare current to the most competitive so far
                for index in range(subsequence_length):
                    if current_subsequence[index] < most_competitive_subsequence[index]:

                        most_competitive_subsequence = current_subsequence
                        break

                    #If current subsequence is not better, move on
                    elif current_subsequence[index] > most_competitive_subsequence[index]:
                        break

    return most_competitive_subsequence

Big(O) Analysis

Time Complexity

O(2^n * k) – The algorithm considers every possible subsequence of the input array nums of size n. There are 2^n possible subsequences because each element can either be included or excluded. For each subsequence, we check if its length is equal to k. If it is, we compare it with the current 'most competitive' subsequence, which involves comparing up to k elements. Therefore, the overall time complexity is O(2^n * k), where 2^n represents the number of subsequences considered, and k represents the length of the subsequences being compared.

Space Complexity

O(N) – The provided brute force approach explores all possible subsequences. The 'most competitive' subsequence found so far needs to be stored, which can have a length of up to K (where K is an input to the original problem, assumed to be less than or equal to N, where N is the length of the input sequence). Since K can be at most N, the space required to store this subsequence grows linearly with N. Therefore, the space complexity is O(N).

Optimal Solution

Approach

To find the most competitive subsequence, imagine you're building the subsequence one element at a time, always picking the smallest available number while ensuring you have enough numbers left to complete the subsequence. We use a special data structure that lets us quickly identify and remove larger, less competitive numbers that are no longer needed.

Here's how the algorithm would work step-by-step:

Imagine we're building our subsequence one number at a time.
We need to go through the original sequence from left to right.
As we look at each number, we want to keep it only if it makes the subsequence better.
If the number is smaller than the last number we picked, and we still have enough numbers left in the original sequence to complete our subsequence, we can remove the last number and take the new smaller number instead.
We keep repeating this check: if the current number is smaller and we have enough numbers left, remove the last selected number and add the current number.
Otherwise, if we don't remove the last selected number, we simply add the current number to our subsequence only if there's space left.
By always prioritizing smaller numbers and making sure we can still complete the subsequence, we find the most competitive result.

Code Implementation

def find_most_competitive_subsequence(numbers, subsequence_length):
    stack = []
    numbers_to_remove = len(numbers) - subsequence_length

    for i, number in enumerate(numbers):
        # Maintain the stack to ensure competitiveness.
        while stack and number < stack[-1] and numbers_to_remove > 0:
            stack.pop()
            numbers_to_remove -= 1

        # Only add if there's space.
        if len(stack) < subsequence_length:

            stack.append(number)

    # Ensure correct length if removals were insufficient.
    while numbers_to_remove > 0 and stack:
        stack.pop()
        numbers_to_remove -= 1

    return stack

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input array `nums` of size `n` once. Within the loop, the core operation is comparing the current element with the last element in our subsequence (represented by a stack or similar data structure). The while loop removes larger elements from the subsequence. Although there's a while loop, each element in the input array is added to and removed from the stack at most once. Therefore, the amortized cost of the while loop is O(1). Thus, the overall time complexity is dominated by the single pass through the input array, resulting in O(n).

Space Complexity

O(k) – The algorithm maintains a subsequence of length k. This subsequence is stored in an auxiliary data structure, such as a list or a stack, to facilitate the selection and potential removal of elements as described. Therefore, the space required is proportional to the length of the desired subsequence, k. Thus, the space complexity is O(k).

Edge Cases

Case	How to Handle
Empty input array nums or k <= 0	Return an empty array if nums is empty or k is non-positive.
k is equal to the length of nums	Return the original nums array as the most competitive subsequence.
nums contains only identical values	The subsequence will consist of the first k identical values.
nums is sorted in descending order	The subsequence will consist of the first k elements of the sorted array.
nums contains negative and positive numbers	The algorithm should handle both positive and negative numbers correctly by comparing their values.
Large input array size with small k (k << len(nums))	Use a stack-based approach to maintain the potential subsequence to achieve O(N) time complexity.
Input array contains very large numbers close to integer limits	Ensure that comparisons don't cause integer overflow and the language's integer comparison handles large numbers correctly.
Multiple equally competitive subsequences exist	The algorithm inherently finds the lexicographically smallest among equally competitive subsequences due to its left-to-right processing.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Can k be zero or larger than the size of the input array?
If multiple subsequences of length k are equally competitive, is any one acceptable?
Can the input array contain duplicate numbers, and if so, how should they be handled when comparing subsequences?
What should I return if the input array is null or empty, or if k is invalid?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every possible subsequence that could be created from the original sequence.
This means trying every possible combination of including or excluding each number in the original sequence.
For each subsequence, check if its length is what we are looking for.
If the subsequence length is not what we want, ignore it and move on to the next subsequence.
If the subsequence length is correct, compare it to all other subsequences of the correct length that we've seen so far.
Determine which subsequence is 'more competitive' by comparing them element by element until one is found to be better than the other.
Keep track of the 'most competitive' subsequence we've found so far.
After looking at all possible subsequences, return the 'most competitive' one we found.

Code Implementation

def find_most_competitive_subsequence_brute_force(numbers, subsequence_length):
    most_competitive_subsequence = []

    # Generate all possible subsequences
    for i in range(1 << len(numbers)):
        current_subsequence = []
        for j in range(len(numbers)):
            if (i >> j) & 1:
                current_subsequence.append(numbers[j])

        # Only consider subsequences of correct length
        if len(current_subsequence) == subsequence_length:

            # First subsequence of correct length initializes
            if not most_competitive_subsequence:
                most_competitive_subsequence = current_subsequence

            else:
                # Compare current to the most competitive so far
                for index in range(subsequence_length):
                    if current_subsequence[index] < most_competitive_subsequence[index]:

                        most_competitive_subsequence = current_subsequence
                        break

                    #If current subsequence is not better, move on
                    elif current_subsequence[index] > most_competitive_subsequence[index]:
                        break

    return most_competitive_subsequence

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine we're building our subsequence one number at a time.
We need to go through the original sequence from left to right.
As we look at each number, we want to keep it only if it makes the subsequence better.
If the number is smaller than the last number we picked, and we still have enough numbers left in the original sequence to complete our subsequence, we can remove the last number and take the new smaller number instead.
We keep repeating this check: if the current number is smaller and we have enough numbers left, remove the last selected number and add the current number.
Otherwise, if we don't remove the last selected number, we simply add the current number to our subsequence only if there's space left.
By always prioritizing smaller numbers and making sure we can still complete the subsequence, we find the most competitive result.

Code Implementation

def find_most_competitive_subsequence(numbers, subsequence_length):
    stack = []
    numbers_to_remove = len(numbers) - subsequence_length

    for i, number in enumerate(numbers):
        # Maintain the stack to ensure competitiveness.
        while stack and number < stack[-1] and numbers_to_remove > 0:
            stack.pop()
            numbers_to_remove -= 1

        # Only add if there's space.
        if len(stack) < subsequence_length:

            stack.append(number)

    # Ensure correct length if removals were insufficient.
    while numbers_to_remove > 0 and stack:
        stack.pop()
        numbers_to_remove -= 1

    return stack

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array nums or k <= 0	Return an empty array if nums is empty or k is non-positive.
k is equal to the length of nums	Return the original nums array as the most competitive subsequence.
nums contains only identical values	The subsequence will consist of the first k identical values.
nums is sorted in descending order	The subsequence will consist of the first k elements of the sorted array.
nums contains negative and positive numbers	The algorithm should handle both positive and negative numbers correctly by comparing their values.
Large input array size with small k (k << len(nums))	Use a stack-based approach to maintain the potential subsequence to achieve O(N) time complexity.
Input array contains very large numbers close to integer limits	Ensure that comparisons don't cause integer overflow and the language's integer comparison handles large numbers correctly.
Multiple equally competitive subsequences exist	The algorithm inherently finds the lexicographically smallest among equally competitive subsequences due to its left-to-right processing.