LeetCode: Remove K Digits

Problem Statement

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

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

Solution Thought Process

If the string length is k, then we have to remove all the digits, returning "0" as the answer.

int stringLength = num.size();
if (stringLength == k) {
    return "0";
}

This problem uses a pattern that I like to call Stack Squashing. I learned it from a friend of mine, Ahnaf, who now works at Amazon. Suppose you have a stack which currently stores some element. Those elements have some special kind of power. When we are putting elements on the stack, the element which we are putting sees if it is more powerful the top element of the stack, and while it sees that the top element of the stack is less powerful than it, it destroys them. If it has destroyed all the elements less powerful than it and has found a more powerful element than it or the stack has become empty, it gets pushed into the stack.

Let's learn it through the example. Let's keep the elements on the stack which we will consider as the remaining numbers. Here the power we will be considering is the lightness of the element. The smaller the element, the powerful it is.

The number is 1432219, we have to delete 3 elements.

1. First, we put the number 1, because the stack is empty, we push it. It goes to the bottom. We haven't deleted any element.

Stack                    Stack
Bottom  ->               Top
1

1. Next, the element is 4, because top element is powerful than the element, we push it in the stack. We haven't deleted any element.

Stack                    Stack
Bottom  ->               Top
1   4

1. Element is 3, and the top element is less powerful, so we squash/destroy it. After that, the top element is 1, which is more powerful. We have deleted one element.

Stack                    Stack
Bottom  ->               Top
1   3

1. Element is 2, the top element is less powerful, so we squash/destroy it. After that, the top element is 1, which is more powerful. We have deleted two elements.

Stack                    Stack
Bottom  ->               Top
1   2

1. Element is 2, the top element is equal. We push it on the stack.

Stack                    Stack
Bottom  ->               Top
1   2   2

1. Element is 1, the top element is less powerful, so we squash/destroy it. After that, the top element is 2, but we have already deleted 3 elements. So we can't delete more.

Stack                    Stack
Bottom  ->               Top
1   2   1

1. The element is 9. We push it into the stack without thinking anything because we can't delete it.

Stack                    Stack
Bottom  ->               Top
1   2   1   9

There is a caveat on this approach, if all the numbers are of the same power, it would not delete the numbers. Suppose we have some numbers like "1111" and 2 items to delete, following this algorithm will not help us doing so. So we have to add a little edge case handling.

while(n>0)
{
    S.pop();
    n--;
}

Next, we pop from the stack to create the number, the number would be in reverse order.

string result;
while (!S.empty()) {
    char digit = S.top();
    S.pop();
    result += digit;
}

First, we remove all the 0s in the front. Suppose the number in reverse is like this: "000321". We have to remove the first 3 0s then our original number "321" would be there.

while (idx >= 0) {
    char digit = result[idx];
    if (digit - '0' > 0) {
       break;
    }
    result.erase(idx);
    idx--;
}

Next, we reverse the string.

reverse(result.begin(), result.end());

We return the string as the result.

Solution

class Solution {
  public:
    string removeKdigits(string num, int k) {
      int stringLength = num.size();
      if (stringLength == k) {
        return "0";
      }
      stack < char > S;
      int n = k, idx = 0;
      while (idx < stringLength) {
        int currentNumber = num[idx] - '0';
        while(n > 0 && !S.empty() && (S.top()-'0') > currentNumber)
        {
                n--;
                S.pop();
        }
        S.emplace(num[idx]);
        idx++;
      }

      while(n>0)
      {
         S.pop();
         n--;
      }

      string result;
      while (!S.empty()) {
        char digit = S.top();
        S.pop();
        result += digit;
      }


      idx = result.size() - 1;
      while (idx >= 0) {
        char digit = result[idx];
        if (digit - '0' > 0) {
          break;
        }
        result.erase(idx);
        idx--;
      }
      reverse(result.begin(), result.end());
      if(result == "") result = "0";
      return result;
    }
};

Complexity

Time Complexity: O(n), we are iterating over the array once.

Space Complexity: O(n), we have to at most save the whole number in the stack and in the result string.