Remove K Digits Problem

Problem

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

Examples

Example 1:

1
2
3


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:

1
2
3


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:

1
2
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

Method 1 - Monotonic Increasing Stack

Lets figure out the problem with some examples. Example 1

1
2


k = 1, num = 999
Remove any 9, output = 99

Example 2

1
2


k = 1, num = 991
Remove: Any 9, output: 91

Example 3a

1
2


k = 1, num = 911
Remove: 9, output: 11

Example 3b

1
2


k = 1, num = 119
Remove: 9, output: 11

Example 4

1
2


k = 1, num = 919
Remove the most significant digit (MSD) 9, output: 19

So, we prioritise removing the most significant digits when digits are equal, or the largest digit in the array.

So, we are biased towards removing the MSD when digits are equal OR we want to remove the largest number in the array.

Example 5a

1
2


k = 1, num = 54321
We remove MSD in case digits are in decreasing order

Example 5b

1
2


k = 1, num = 12345
This is oppositve example of 5a, here we will not remove 1, but 5 to the smallest number.

Algorithm

We can use Monotonic Increasing Order Stack. We will start from left, as we are biased towards MSD. We will continue to add the values to stack, till they are in increasing order.
If they are not in increasing order, we discard previous digits by popping and decrement k
Remove remaining k chars

For eg. for 12345 , we will add all elements in stack, and then pop out k elements. Then we will just pop out k elements in total when we are done.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


public class Solution {
    public String removeKdigits(String num, int k) {
        int len = num.length();
        // Corner case: If k equals the length of num, return "0"
        if (k == len) {
            return "0";
        }

        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : num.toCharArray()) {
            // Whenever we find a digit smaller than the previous digit, discard the previous one
            while (k > 0 && !stack.isEmpty() && stack.peekLast() > ch) {
                stack.removeLast();
                k--;
            }
            stack.addLast(ch);
        }    

        // Remove remaining chars in case of cases like "1111" or "1234"
        while (k > 0) {
            stack.removeLast();
            k--;
        }

        // Construct the number from the Deque
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.removeFirst());
        }

        // Remove all zeros from the head
        while (sb.length() > 1 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }

        return sb.length() == 0 ? "0" : sb.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        length = len(num)
        # Corner case: if k equals the length of num, return "0"
        if k == length:
            return "0"
        
        stack = deque()
        
        for ch in num:
            # Whenever we find a digit which is smaller than the previous digit, discard the previous one
            while k > 0 and stack and stack[-1] > ch:
                stack.pop()
                k -= 1
            stack.append(ch)
        
        # If k is still greater than 0, discard the remaining largest digits
        while k > 0:
            stack.pop()
            k -= 1
        
        # Construct the final number from the stack
        result = ''.join(stack).lstrip('0')  # Remove leading zeros
        
        return result if result else "0"

Complexity

⏰ Time complexity: O(n), as each character in the string num is processed only once.
🧺 Space complexity: O(n), to store upto n characters in stack in worst case.

Problem#

Examples#

Solution#

Method 1 - Monotonic Increasing Stack#

Algorithm#

Code#

Complexity#