LESSON 335 OF 441 · STACK

Remove K Digits in C#: Greedy Monotonic Stack in O(n)

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.

STEP 1 OF 19

Guided

Ctrl + Enter to check

C# · STACK

Remove K Digits in C#, explained

Problem overview

The method RemoveKdigits receives num, a string of digits that stands for a non-negative integer, and an integer k. It must delete exactly k digits from the string, without reordering the rest, so that the number left is as small as possible. It returns that number as a string, with no leading zeros. If nothing remains, or only zeros, the answer is "0".

For "1432219" with k = 3, removing 4, 3 and 2 leaves "1219", the smallest result. For "10200" with k = 1, removing the 1 leaves "0200", which is written "200" once the leading zero goes. For "10" with k = 2, every digit is removed, and the answer is "0".

Approach: drop a digit that is bigger than its right neighbour

Trying every set of k digits to remove is hopeless for strings of up to 100,000 digits. A greedy rule works instead.

Compare the results of removing one digit. The left end of a number matters most, so the first place where two candidates differ decides which is smaller. Look at a digit and the one right after it. If the digit is bigger than its right neighbour, removing it slides the smaller neighbour into its position, and the number gets smaller. If the digit is smaller or equal, removing it never helps at that position.

So the rule is: scan the digits from left to right and, while the digit just kept is bigger than the digit now being read, remove it, as long as removals are left. A stack does this naturally. Its top is the last digit kept:

For each new digit c, pop the top while k > 0 and the top is greater than c. Each pop uses one removal.
Then push c. It stays until a smaller digit that comes later removes it.

Two leftovers need care:

If removals remain after the scan, the digits never decrease from bottom to top, as in "1234". The biggest digits are then at the end, so pop from the top until k is 0.
The stack can start with zeros, as in "0200". They are skipped when the answer is written, and an empty result becomes "0".

On "1432219", k = 3: the stack grows to 1, 4. The digit 3 pops 4 (k = 2), the next 2 pops 3 (k = 1), then the second 2 is pushed and the 1 pops one 2 (k = 0). The remaining digits are pushed without further checks, and the stack ends as 1, 2, 1, 9.

Step by step

Create a List<char> named stack. Its end is the top: Add pushes, and RemoveAt(stack.Count - 1) pops. A List is used rather than Stack<char> because the output step reads the digits from bottom to top, and a Stack enumerates from the top.
Loop over the digits of num with foreach, using c for the current one.
Pop while it helps. The inner while runs while k > 0, the stack is not empty and its top is greater than c.
Remove the top with RemoveAt(stack.Count - 1).
Decrease k, since one removal is used.
Push c with Add.
Use the leftover removals. After the scan, a second loop runs while k > 0.
Pop the top digit in it: the stack never decreases from bottom to top at this point, so the top is the biggest digit.
Decrease k again.
Return the result of a helper, JoinWithoutLeadingZeros(stack).
Declare the helper as a private method taking the List<char> and returning a string.
Create startingZeros, a bool that is true while only zeros have been seen.
Create a StringBuilder named result. Appending to it doesn't copy the whole text each time, as repeated + on strings would.
Loop over the stack with foreach, which goes from the first element to the last: the order of the digits in the number.
Check for a digit other than '0'.
Turn startingZeros off in that case. It stays off, so the zeros in "200" are kept.
Check !startingZeros.
Append the digit to result.
Return "0" for an empty result and result.ToString() otherwise, with the ternary operator.

The solution in C#

class Solution {
    public string RemoveKdigits(string num, int k) {
        List<char> stack = new List<char>();
        foreach (char c in num) {
            while (k > 0 && stack.Count > 0 && stack[stack.Count - 1] > c) {
                stack.RemoveAt(stack.Count - 1);
                k--;
            }
            stack.Add(c);
        }
        while (k > 0) {
            stack.RemoveAt(stack.Count - 1);
            k--;
        }
        return JoinWithoutLeadingZeros(stack);
    }
    private string JoinWithoutLeadingZeros(List<char> stack) {
        bool startingZeros = true;
        StringBuilder result = new StringBuilder();
        foreach (char ch in stack) {
            if (ch != '0') {
                startingZeros = false;
            }
            if (!startingZeros) {
                result.Append(ch);
            }
        }
        return result.Length == 0 ? "0" : result.ToString();
    }
}

The C# details worth knowing:

Characters compare by code. char supports > and <, and the digit characters '0' to '9' have increasing codes, so '9' > '1' is true, just like 9 > 1. The solution never converts the digits to numbers.
RemoveAt on the last index is cheap. Removing from the end of a List doesn't shift any elements. Removing from the front would, and it would make the method slow.
foreach over a string gives its characters one by one. It reads num and doesn't change it, since strings are immutable. The parameter k can be changed freely: it is a local copy of the argument.
List<char> and StringBuilder need namespaces. They come from System.Collections.Generic and System.Text, so a standalone file needs the matching using lines.
The ternary operator cond ? a : b is an expression, so it can sit right after return. Both branches here are strings.
Why the second loop is safe. The constraints give k <= num.Length, so the stack never runs out of digits to pop. The stack holds num.Length minus the digits already removed, which is at least the k that remains.

Complexity

Let n be the length of num.

Time: O(n). Every digit is pushed once and popped at most once, so the two loops together do at most about 2n stack operations. The helper makes one more pass over the stack.

Space: O(n). The stack and the StringBuilder each hold up to n characters.

Edge cases and common mistakes

Everything removed. "10" with k = 2 empties the stack, and the helper returns "0".
Leading zeros appear after removal. "10200" with k = 1 leaves 0, 2, 0, 0 on the stack, and the output is "200". Zeros after the first non-zero digit stay.
All zeros left. "100" with k = 1 leaves 0, 0, which has no non-zero digit, so the answer is "0".
Increasing digits. "1234" with k = 2 never pops during the scan, and the second loop removes 4 and 3, giving "12". Forgetting that loop returns a string that is too long.
Equal digits. "1111" with k = 2 gives "11". The comparison is strict (>), so equal digits are not popped during the scan, and the second loop removes the last ones.
Decreasing digits. "54321" with k = 2 gives "321": each new digit pops the one before it until k runs out.
Comparing as numbers. The input can have 100,000 digits, far more than an int or long can hold, so the digits have to stay characters.
Returning an empty string. The answer for no remaining digits is "0", not "".

Testing

"1432219" with k = 3 gives "1219".
"10200" with k = 1 gives "200".
"10" with k = 2 gives "0".
"1234" with k = 2 gives "12".
"112" with k = 1 gives "11".
"10001" with k = 4 gives "0".

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free