Jobs

Interviews

Discussions

Remove K Digits

Medium

Coupang

0 views

Topics:

StringsGreedy AlgorithmsStacks

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Constraints:

1 <= k <= num.length <= 10⁵
num consists of only digits.
num does not have any leading zeros except for the zero itself.

Remove K Digits

Medium

Coupang

0 views

Topics:

StringsGreedy AlgorithmsStacks

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Constraints:

1 <= k <= num.length <= 10⁵
num consists of only digits.
num does not have any leading zeros except for the zero itself.

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 for each digit in the input string num, and is num guaranteed to contain only digits?
Can the integer k (number of digits to remove) be zero, negative, or greater than or equal to the length of the input string num?
If after removing k digits, the resulting number has leading zeros, should I remove them? Should the final result be an empty string if all digits are removed?
Are there any constraints on the length of the input string num (e.g., minimum or maximum length)?
If there are multiple valid results after removing k digits, is there a specific criterion for selecting the optimal one, or can I return any valid result?

Brute Force Solution

Approach

The brute force strategy for removing digits involves examining every possible combination of digit removals. We generate each possible result of removing the specified number of digits from the original number. We then compare these results to identify the smallest remaining number.

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

Consider all the different ways you can remove the specified number of digits from the given number.
For each possible combination of removals, create the resulting number.
Compare all the created numbers.
Select the smallest number among all the possible results. This will be your answer.

Code Implementation

def remove_k_digits_brute_force(number_string, k_digits):
    from itertools import combinations

    number_length = len(number_string)
    if k_digits == number_length:
        return "0"

    # Generate all possible combinations of indices to keep
    indices_to_keep_combinations = combinations(range(number_length), number_length - k_digits)

    smallest_number = None

    for indices_to_keep in indices_to_keep_combinations:
        # Build the number from the selected indices
        resulting_number = "".join(number_string[index] for index in indices_to_keep)

        # Remove leading zeros
        resulting_number = resulting_number.lstrip('0')
        if not resulting_number:
            resulting_number = "0"

        # Compare with the current smallest number
        if smallest_number is None or int(resulting_number) < int(smallest_number):
            #Because we need to keep track of the smallest at all times
            smallest_number = resulting_number

    return smallest_number

Big(O) Analysis

Time Complexity

O(C(n, k)) – The brute force approach involves considering all possible combinations of removing k digits from the n-digit number. The number of such combinations is given by the binomial coefficient C(n, k), which represents 'n choose k'. Generating each combination takes some amount of work. Comparing all these combinations to find the minimum also takes work dependent on the size of C(n,k). Therefore the runtime is directly proportional to the number of combinations, C(n, k), which is O(n! / (k! * (n-k)!)). Because factorial growth is faster than polynomial, the leading term is O(C(n, k)).

Space Complexity

O(N choose K) – The brute force solution generates all possible combinations of removing K digits from the N-digit number. This involves creating each possible resulting number after removing K digits, which can be represented as a string or a list of digits. The number of these combinations is given by the binomial coefficient 'N choose K', which is N! / (K! * (N-K)!). Therefore, the algorithm needs to store all these generated numbers, resulting in space proportional to the number of combinations. Since we are storing each combination explicitly, the auxiliary space required to store all these combinations is O(N choose K).

Optimal Solution

Approach

The goal is to create the smallest possible number by removing some digits. The trick is to greedily remove digits that are larger than their immediate following digit, effectively eliminating the 'peaks' from left to right. This ensures we are always making locally optimal choices that lead to the smallest overall number.

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

Imagine you are building the smallest number digit by digit from left to right.
Look at the digits one by one. If a digit is bigger than the digit right after it, get rid of it. This is because a smaller digit later in the sequence is always preferable to a bigger digit earlier in the sequence.
Keep doing this until you've removed the required number of digits.
If you run out of 'peaks' to remove (meaning the digits are in increasing order), simply remove digits from the end, as the rightmost digits have the least impact.
Finally, remove any leading zeros from the result to get the actual smallest number.

Code Implementation

def remove_k_digits(number, k):
    stack = []

    for digit in number:
        # Remove larger preceding digits to maintain a non-decreasing sequence
        while stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1

        stack.append(digit)

    # If we still need to remove digits, remove from the end.
    while k > 0:
        stack.pop()
        k -= 1

    result = "".join(stack)

    # Remove leading zeros.
    result = result.lstrip('0')

    # Handle the case where all digits are removed.
    return result if result else "0"

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n at most once, using a stack to maintain the digits of the result. In the worst case, each digit is pushed onto the stack and potentially popped off once, leading to a maximum of 2n stack operations. Removing leading zeros also takes at most n operations. Therefore, the time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a stack (implicitly or explicitly, based on the implementation of 'building the smallest number digit by digit') to store the digits that form the potential smallest number. In the worst case, where the digits are in strictly increasing order, the stack will contain all N digits of the input number before removals from the end begin. Therefore, the auxiliary space used by the stack is proportional to the input size N, making the space complexity O(N).

Edge Cases

Case	How to Handle
Null or empty string input	Return '0' if the input string is null or empty, as there are no digits to keep.
k is zero	Return the original number string since no digits need to be removed.
k is equal to the length of the number string	Return '0' since all digits must be removed, resulting in an empty number.
Number string consists of all identical digits (e.g., '11111')	Remove k digits from the end, resulting in a string of the remaining identical digits or '0' if k equals the number's length.
The number string is already in ascending order (e.g., '12345')	Remove k digits from the end of the string as those are the largest to keep the smallest number.
Leading zeros after removing digits (e.g., removing 1 digit from '10200' to get '0200')	Remove leading zeros from the final result string after removing the specified number of digits.
Large input string and large k causing potential performance issues	Use a stack-based approach for optimal O(n) time complexity to handle large inputs efficiently.
Input contains non-digit characters	Throw an IllegalArgumentException, as the problem specifies a number string.

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 for each digit in the input string num, and is num guaranteed to contain only digits?
Can the integer k (number of digits to remove) be zero, negative, or greater than or equal to the length of the input string num?
If after removing k digits, the resulting number has leading zeros, should I remove them? Should the final result be an empty string if all digits are removed?
Are there any constraints on the length of the input string num (e.g., minimum or maximum length)?
If there are multiple valid results after removing k digits, is there a specific criterion for selecting the optimal one, or can I return any valid result?

Brute Force Solution

Approach

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

Consider all the different ways you can remove the specified number of digits from the given number.
For each possible combination of removals, create the resulting number.
Compare all the created numbers.
Select the smallest number among all the possible results. This will be your answer.

Code Implementation

def remove_k_digits_brute_force(number_string, k_digits):
    from itertools import combinations

    number_length = len(number_string)
    if k_digits == number_length:
        return "0"

    # Generate all possible combinations of indices to keep
    indices_to_keep_combinations = combinations(range(number_length), number_length - k_digits)

    smallest_number = None

    for indices_to_keep in indices_to_keep_combinations:
        # Build the number from the selected indices
        resulting_number = "".join(number_string[index] for index in indices_to_keep)

        # Remove leading zeros
        resulting_number = resulting_number.lstrip('0')
        if not resulting_number:
            resulting_number = "0"

        # Compare with the current smallest number
        if smallest_number is None or int(resulting_number) < int(smallest_number):
            #Because we need to keep track of the smallest at all times
            smallest_number = resulting_number

    return smallest_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you are building the smallest number digit by digit from left to right.
Look at the digits one by one. If a digit is bigger than the digit right after it, get rid of it. This is because a smaller digit later in the sequence is always preferable to a bigger digit earlier in the sequence.
Keep doing this until you've removed the required number of digits.
If you run out of 'peaks' to remove (meaning the digits are in increasing order), simply remove digits from the end, as the rightmost digits have the least impact.
Finally, remove any leading zeros from the result to get the actual smallest number.

Code Implementation

def remove_k_digits(number, k):
    stack = []

    for digit in number:
        # Remove larger preceding digits to maintain a non-decreasing sequence
        while stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1

        stack.append(digit)

    # If we still need to remove digits, remove from the end.
    while k > 0:
        stack.pop()
        k -= 1

    result = "".join(stack)

    # Remove leading zeros.
    result = result.lstrip('0')

    # Handle the case where all digits are removed.
    return result if result else "0"

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return '0' if the input string is null or empty, as there are no digits to keep.
k is zero	Return the original number string since no digits need to be removed.
k is equal to the length of the number string	Return '0' since all digits must be removed, resulting in an empty number.
Number string consists of all identical digits (e.g., '11111')	Remove k digits from the end, resulting in a string of the remaining identical digits or '0' if k equals the number's length.
The number string is already in ascending order (e.g., '12345')	Remove k digits from the end of the string as those are the largest to keep the smallest number.
Leading zeros after removing digits (e.g., removing 1 digit from '10200' to get '0200')	Remove leading zeros from the final result string after removing the specified number of digits.
Large input string and large k causing potential performance issues	Use a stack-based approach for optimal O(n) time complexity to handle large inputs efficiently.
Input contains non-digit characters	Throw an IllegalArgumentException, as the problem specifies a number string.