Remove k digits for the smallest number

Why this matters

Suppose a program receives a long number as text, such as 1432219, and it must delete exactly three digits. The digits that remain keep their original order. The goal is the smallest number that can be left. You could delete 4, 3 and 2 to get 1219, or delete 1, 4 and 3 to get 2219. The first answer is smaller, and the question is how to find it quickly for any string.

This is a standard practice problem, and it shows a useful technique. A stack is a pile of items where you only add and remove at the top. A monotonic stack is a stack whose items stay in order, either always going up or always going down, as you push new items. The method here keeps a stack that goes up, and it uses a greedy rule for when to pop an item off the top.

A greedy algorithm makes the best choice it can see at each step and does not go back. This lesson needs only C++ strings, which are std::string values that hold text, and a few functions on them. Each one is explained where it is used.

The problem in plain words

You get two things. The first is a string num made only of digits, such as "1432219". The second is a whole number k, the count of digits to remove. Remove exactly k digits, keep the others in their original order, and return the smallest number that remains. The answer is also a string.

Two rules make the answer tidy. A number should not start with zeros, so "0200" becomes "200". If every digit is removed, the answer is "0", because an empty string would not be a number.

Trying every choice is one option. For 1432219 with k = 3, you keep 4 of the 7 digits, and there are 35 ways to choose which four to keep. The count of choices grows very fast as the string gets longer, so a longer number needs a better method.

The key idea: the left digit matters most

Compare two numbers with the same number of digits. The number is decided by its leftmost digit first. If the first digits differ, the number with the smaller first digit is smaller, and the rest of the digits do not matter. Only if the first digits are equal does the second digit decide, and so on.

This gives the greedy rule. Look at a digit and the digit after it. If the first is bigger, removing the first makes the number smaller at that position. For example, take 1432. The digits 4 and 3 are in the wrong order for a small number, because 4 comes before a smaller 3. Removing the 4 from 1432 leaves 132. Removing the 3 instead leaves 142. Compare the two results from the left: the first two digits are 13 against 14, so 132 is the smaller one. A bigger digit followed by a smaller one is a good place to remove from.

The scan works like this. Walk through the digits from left to right and push each one onto a stack. Before pushing a new digit, look at the top of the stack. While the top is bigger than the new digit and you still have digits to remove, pop the top and count one removal. Then push the new digit. The stack therefore stays in non-decreasing order, which means each digit is at least as big as the one before it, until you run out of removals.

Worked example one: 1432219 with k = 3

The table below traces the scan on 1432219 with k set to 3. The column "stack" shows the text in the stack after each step, with the top on the right.

After the last digit, the stack holds 1219, and no removals are left, so the answer is 1219. Here is the output of a version of the scan that prints one line per digit, for the same run. The k at the end of each line is the removals left after that step.

digit 1, stack before="", stack after="1" k=3
digit 4, stack before="1", stack after="14" k=3
digit 3, stack before="14" pop 4, stack after="13" k=2
digit 2, stack before="13" pop 3, stack after="12" k=1
digit 2, stack before="12", stack after="122" k=1
digit 1, stack before="122" pop 2, stack after="121" k=0
digit 9, stack before="121", stack after="1219" k=0
end: stack="1219" k=0
1219

The digit 4 is pushed on top of 1, because the rule pops only a bigger top, and 1 is smaller. The digit 3 is the first real removal: the top 4 is bigger than 3, so the 4 is popped.

What to do with leftover removals

Sometimes the scan ends with removals still to spend. This happens when the digits are already in non-decreasing order, such as 12345. Nothing was popped, because no digit was smaller than the one before it. In that case the rightmost digits are the largest, so remove from the end of the stack. Removing the last two digits of 12345 leaves 123, which is the smallest number possible with three digits taken from this order.

The program handles this with one line: erase the last k characters of the stack. Because the stack is in non-decreasing order, those are the largest digits, so the result is the smallest.

Worked example two: leading zeros

Take 10200 with k = 1. The scan works like this. Push 1. The next digit is 0, which is smaller than the top 1, and one removal is left, so pop the 1. The stack is now empty, so push 0. The next digits are 2, then 0. The removals are used up, so both are pushed. The stack holds 0200.

The answer is not 0200, because a number does not start with zeros. Remove the leading zeros to get 200. The text 0200 and the text 200 have the same value, and 200 is the form a program should print.

Here is a larger leading-zero case. Take 1000200 with k = 1. The first 1 is popped by the 0 that follows it, and the stack then holds 000200. Stripping the leading zeros gives 200.

Worked example three: a falling run

Take 9876543 with k = 3. The digits go down from 9 to 3. Each new digit is smaller than the top of the stack, so it pops the top while removals remain.

• Push 9. The stack is 9.
• The digit 8 is smaller than 9. Pop 9, one removal used, two left. Push 8.
• The digit 7 is smaller than 8. Pop 8, one removal left. Push 7.
• The digit 6 is smaller than 7. Pop 7, no removals left. Push 6.
• The digits 5, 4 and 3 arrive, but there are no removals left, so each is pushed.

The stack is 6543, which is the answer. Notice that the scan removed the three largest digits, one at a time, because each one sat in front of a smaller digit. If a digit had come after a larger digit and no removals were left, the scan would keep it.

Worked example four: the whole number is removed

Take 10 with k = 2. Push 1. The digit 0 is smaller than 1, so pop 1, which leaves one removal. Push 0. The stack is 0. One removal is still left, so erase the last character, and the stack is empty. The stripping step finds no digit that is not zero, so the answer is "0". Without that special case the function would return an empty string.

Writing it in C++

Here is the full function. The stack is a std::string. The back() function returns the last character, which is the top of the stack. push_back adds a character to the end, and pop_back removes it. The function uses std::string_view for the input, which means it reads the characters without copying them.

#include <iostream>
#include <string>
#include <string_view>
 
std::string removeKdigits(std::string_view num, int k) {
    std::string kept;  // back() is the top of the stack
    for (char digit : num) {
        while (k > 0 && !kept.empty() && kept.back() > digit) {
            kept.pop_back();
            --k;
        }
        kept.push_back(digit);
    }
    // The digits are now in non-decreasing order, so the largest ones sit at the end.
    kept.erase(kept.size() - static_cast<std::size_t>(k));
 
    // Drop leading zeros.
    std::size_t first = kept.find_first_not_of('0');
    if (first == std::string::npos) {
        return "0";
    }
    return kept.substr(first);
}
 
int main() {
    struct Case { std::string_view num; int k; };
    const Case cases[] = {
        {"1432219", 3}, {"10200", 1}, {"10", 2}, {"9876543", 3}, {"1000200", 1},
        {"12345", 2}, {"112", 1}, {"1221", 1}, {"4321", 4}, {"100", 1}, {"7", 1},
    };
    for (const auto& c : cases) {
        std::cout << c.num << " k=" << c.k << " -> " << removeKdigits(c.num, c.k) << '\n';
    }
}

Compile and run it.

g++ -std=c++20 -Wall -Wextra -o removek removek.cpp
./removek

The output is:

1432219 k=3 -> 1219
10200 k=1 -> 200
10 k=2 -> 0
9876543 k=3 -> 6543
1000200 k=1 -> 200
12345 k=2 -> 123
112 k=1 -> 11
1221 k=1 -> 121
4321 k=4 -> 0
100 k=1 -> 0
7 k=1 -> 0

The kept.erase(...) line deserves a note. The value k is an int, and kept.size() is a std::size_t, which is an unsigned number. The cast static_cast<std::size_t>(k) makes the subtraction use the same type. The stack always holds at least k characters at this point, because the number of digits is at least the original k, and every removal so far took one digit away. So the subtraction never goes below zero.

Checking the answer

A good way to check a fast method is to compare it with a slow method on small inputs. The slow method tries every way to remove k digits and keeps the smallest result. A check that compared the two on every digit string of length 1 to 5, with every value of k, covered 654,320 cases. The fast function gave the same answer as the slow method in every one of them. Running the slow method on a few hand-picked cases, such as 112 with k = 1, is a quick check you can do without a script.

Mistakes

Using >= instead of >. The rule pops only when the top is bigger than the new digit. If you pop when the top is equal or bigger, a removal is spent on a digit that is the same as the next one. Here is the change in the comparison, with everything else the same.

while (k > 0 && !kept.empty() && kept.back() >= digit) {

With this change, 112 with k = 1 returns 12. The correct answer is 11. The first 1 is pushed, the second 1 pops the first and uses the removal, and the 2 then has no removals left, so it stays.

Forgetting to remove from the end. Without the erase line, 12345 with k = 2 returns 12345. Here the scan finishes with two removals still unused, and the result is the full string. The program then prints a number with the wrong length.

Forgetting to strip leading zeros. Without the stripping step, 10200 with k = 1 returns 0200. This is the right digits, but the wrong text for a number, and a test that compares strings will fail.

Not handling an all-zero result. Without the special case, 10 with k = 2 returns an empty string. A program that prints the result shows an empty line where the answer 0 belongs.

Calling substr with npos. The function find_first_not_of returns the constant std::string::npos when every character matches the pattern. If the code calls substr with that value, the program stops with an error. Here is a short program that does this on the string 00, compiled with the standard flags and run.

#include <iostream>
#include <string>
 
int main() {
    std::string zeros = "00";
    std::size_t first = zeros.find_first_not_of('0');
    std::cout << zeros.substr(first) << std::endl;
}

The program stops with this message.

terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::substr: __pos (which is 18446744073709551615) > this->size() (which is 2)

The number 18446744073709551615 is the largest unsigned value, which is what npos holds. The check if (first == std::string::npos) in the function prevents this crash.

What the stack holds after each step

After each digit, the stack holds the smallest number that can be made from the digits read so far, using the removals spent so far. This is why the method works, and it helps when you debug a wrong answer by checking the stack after each line of the trace.

Take 1432219 again after the digit 3. The digits read so far are 1, 4 and 3, and one removal has been spent on the 4. The smallest two-digit number that can be made from 1, 4 and 3 is 13, and the stack holds exactly 13.

Each pop is a removal that makes the number smaller at a position the stack already holds. When the digit 3 arrives, the removal of the 4 makes the stack 13 instead of 14. The 1 in front is never removed, because nothing before it can be made smaller by a later digit.

Complexity

Each digit is pushed once and popped at most once. The total number of pushes is n, the number of digits. The total number of pops is also at most n. So the time is proportional to n, which is written O(n). The stack takes up to n characters of space. Building the final result with substr makes one more copy of at most n characters.

Practice

Work each exercise by hand first, then check with the function.

1. Find the answer for 1234 with k = 1.

Show the answer

The digits are already increasing, so nothing is popped during the scan. The stack is 1234 with one removal left. Erase the last digit to get 123.

2. Find the answer for 5432 with k = 2.

Show the answer

Push 5. The digit 4 pops 5 (one removal left) and is pushed. The digit 3 pops 4 (no removals left) and is pushed. The digit 2 has no removals left, so it is pushed. The stack is 32. The answer is 32.

3. Find the answer for 10001 with k = 1.

Show the answer

Push 1. The digit 0 pops 1, which uses the only removal, and is pushed. The three zeros and the final 1 are pushed without removals. The stack is 0001. Stripping the leading zeros gives 1.

4. Find the answer for 2736 with k = 2. Explain why the answer is not 36.

Show the answer

Push 2 and push 7. The digit 3 pops 7 (one removal left) and is pushed, so the stack is 23. The digit 6 is bigger than 3, so it is pushed, and the stack is 236. One removal is still left, so erase the last digit to get 23. The answer is 23. The answer 36 would delete the 2 and the 7, which is a valid choice, but 23 is smaller because its first digit is 2 and 36 starts with 3.

5. The version with >= returns 12 for 112 with k = 1. Explain which digit was removed by mistake, and what the correct removal is.

Show the answer

The second 1 pops the first 1, which is equal to it, and uses the only removal. The stack becomes 1, and then 2 is pushed with no removals left, so the result is 12. The correct removal is the 2 at the end, which leaves 11. Using a removal on equal digits wastes it, because removing either of two equal digits gives the same text.

Summary

• Keep a stack of digits that goes up, and pop the top when a smaller digit arrives and removals remain.
• The leftmost digit decides a number's size first, so removing a bigger digit before a smaller one helps most.
• After the scan, remove any leftover removals from the end of the stack.
• Strip leading zeros, and return "0" when nothing is left.
• The method runs in time proportional to the number of digits, while trying every choice grows far faster.
• Use > for the pop test, not >=, because >= wastes removals on equal digits.