Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Remove K Digits

MEDIUMProblemSolveExternal Links

Description

You are given a string num that represents a non-negative integer, and an integer k. Your task is to remove exactly k digits from num so that the resulting number is as small as possible.

Return the smallest possible number as a string. The result must not contain leading zeros, except when the result itself is zero (in which case return "0").

The digits you keep must remain in the same relative order as they appeared in the original string.

Examples

Example 1

Input: num = "1432219", k = 3

Output: "1219"

Explanation: By removing the digits 4, 3, and the first 2, the remaining digits form 1219. No smaller four-digit number can be produced from the original sequence while preserving order.

Example 2

Input: num = "10200", k = 1

Output: "200"

Explanation: Removing the leading 1 yields "0200". After stripping the leading zero, the result is "200". This is smaller than removing any other single digit (e.g., removing 0 gives "1200", removing 2 gives "1000").

Example 3

Input: num = "10", k = 2

Output: "0"

Explanation: Both digits are removed, leaving nothing. An empty result is represented as "0".

Constraints

  • 1 ≤ k ≤ num.length ≤ 10^5
  • num consists of only digits.
  • num does not have any leading zeros except for the zero itself.

Editorial

Brute Force

Intuition

When comparing two numbers with the same number of digits, the leftmost (most significant) digits matter the most. For instance, 1999 is smaller than 2000 because the very first digit 1 < 2.

This gives us a key observation: if we encounter a digit that is larger than the digit immediately after it, removing the larger digit will always produce a smaller number. For example, in "143...", the 4 is followed by 3. Removing 4 turns the prefix from "14..." into "13...", which is strictly smaller.

The brute-force strategy applies this greedy rule one removal at a time. In each round, we scan from left to right and find the first position where a digit is greater than its right neighbour. We remove that digit, rebuild the string, and repeat until all k removals are used.

If the entire number is non-decreasing (e.g., "12345"), no such drop exists during a scan, so we remove the last digit instead — because in a non-decreasing sequence, the rightmost digit is the largest and contributes the least to making the number small.

Step-by-Step Explanation

Let's trace through with num = "1432219", k = 3:

Round 1 (k = 3):

  • Current string: "1432219"
  • Scan left to right for first drop:
    • Compare '1' and '4': 1 ≤ 4 → continue
    • Compare '4' and '3': 4 > 3 → found! Remove '4' at index 1
  • String becomes: "132219"
  • k decreases to 2

Round 2 (k = 2):

  • Current string: "132219"
  • Scan for first drop:
    • Compare '1' and '3': 1 ≤ 3 → continue
    • Compare '3' and '2': 3 > 2 → found! Remove '3' at index 1
  • String becomes: "12219"
  • k decreases to 1

Round 3 (k = 1):

  • Current string: "12219"
  • Scan for first drop:
    • Compare '1' and '2': 1 ≤ 2 → continue
    • Compare '2' and '2': 2 ≤ 2 → continue
    • Compare '2' and '1': 2 > 1 → found! Remove '2' at index 2
  • String becomes: "1219"
  • k decreases to 0

Result: k = 0, no more removals needed. Strip leading zeros (none here). Return "1219".

Notice that each round requires a full scan from the start of the string. In round 3, we had to check three pairs before finding the drop. This repeated scanning is what makes this approach slower than necessary.

Algorithm

  1. Repeat k times:
    a. Scan the string from left to right
    b. Find the first index i where num[i] > num[i+1]
    c. If no such index exists, set i to the last position
    d. Remove the character at index i
  2. Strip leading zeros from the result
  3. If the result is empty, return "0"

Code

class Solution {
public:
    string removeKdigits(string num, int k) {
        while (k > 0) {
            int i = 0;
            while (i < (int)num.size() - 1 && num[i] <= num[i + 1]) {
                i++;
            }
            num.erase(i, 1);
            k--;
        }
        // Strip leading zeros
        int start = 0;
        while (start < (int)num.size() - 1 && num[start] == '0') {
            start++;
        }
        return num.empty() ? "0" : num.substr(start);
    }
};
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        for _ in range(k):
            i = 0
            while i < len(num) - 1 and num[i] <= num[i + 1]:
                i += 1
            num = num[:i] + num[i + 1:]
        return num.lstrip('0') or '0'
class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder sb = new StringBuilder(num);
        while (k > 0) {
            int i = 0;
            while (i < sb.length() - 1 && sb.charAt(i) <= sb.charAt(i + 1)) {
                i++;
            }
            sb.deleteCharAt(i);
            k--;
        }
        // Strip leading zeros
        while (sb.length() > 1 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

Complexity Analysis

Time Complexity: O(k × n)

We perform k rounds. Each round scans up to n characters to find the first drop and then removes one character (which involves shifting subsequent characters). Both the scan and the removal are O(n). Over k rounds the total work is O(k × n).

In the worst case k is close to n, making this O(n²). For n = 10⁵ and k = 5 × 10⁴, that is roughly 5 × 10⁹ operations — far too slow.

Space Complexity: O(n)

We store the modified string. In-place approaches still need O(n) for the string buffer or character array.

Why This Approach Is Not Efficient

The brute-force approach rescans the string from the beginning in every round. After removing a digit in round 1, the next drop in round 2 might be right next to where the last removal happened — yet we start scanning from index 0 again.

For example, in "1432219" the removals in rounds 1, 2, and 3 all happen near the front of the string. If we remembered our position instead of starting over, we could handle all three removals in a single left-to-right pass.

This is exactly what a stack provides. Instead of k separate scans, we push digits onto a stack and pop whenever the top of the stack is larger than the incoming digit (and we still have removals left). By the time we finish scanning the string once, all k removals are complete. This reduces the time from O(k × n) to O(n).

Optimal Approach - Monotonic Stack

Intuition

The brute force already uses the correct greedy rule — remove the first digit that is bigger than the digit after it. The inefficiency lies in rescanning from the beginning every time. A stack lets us remember where we left off.

Picture building the result digit by digit. You maintain a growing sequence on a notepad (the stack). Each time a new digit arrives:

  • If the new digit is smaller than the last digit you wrote, cross out that last digit (pop) — it was making your number unnecessarily large. Keep crossing out as long as the new digit is still smaller than the latest remaining digit and you have not yet used all k removals.
  • Then write the new digit at the end.

When you finish reading all digits, your notepad contains digits in roughly increasing order from left to right — the ideal shape for a small number. If you still have unused removals (because the original number was already non-decreasing), simply trim digits from the right end, since those are the largest.

Finally, strip any leading zeros and handle the edge case of an empty result.

Step-by-Step Explanation

Let's trace through with num = "1432219", k = 3. We need to keep remain = 7 − 3 = 4 digits.

Step 1: Initialize an empty stack. k = 3, remain = 4.

Step 2: Process '1' (index 0). Stack is empty, push '1'. Stack: ['1'].

Step 3: Process '4' (index 1). '4' ≥ '1' (stack top), so no pop needed — the digit maintains increasing order. Push '4'. Stack: ['1', '4'].

Step 4: Process '3' (index 2). '3' < '4' (stack top). Pop '4' because keeping 4 before 3 makes the number larger than necessary. k decreases: 3 → 2. Stack after pop: ['1'].

Step 5: '3' ≥ '1' (new stack top), so no more pops. Push '3'. Stack: ['1', '3'].

Step 6: Process '2' (index 3). '2' < '3' (stack top). Pop '3'. k: 2 → 1. Stack: ['1'].

Step 7: '2' ≥ '1' (new stack top), stop popping. Push '2'. Stack: ['1', '2'].

Step 8: Process '2' (index 4). '2' = '2' (stack top). Equal means no pop — the number would not shrink by removing an equal digit. Push '2'. Stack: ['1', '2', '2'].

Step 9: Process '1' (index 5). '1' < '2' (stack top). Pop '2'. k: 1 → 0. Stack: ['1', '2'].

Step 10: k = 0, no more removals allowed. Push '1'. Stack: ['1', '2', '1'].

Step 11: Process '9' (index 6). k = 0, just push. Stack: ['1', '2', '1', '9']. All digits processed. Take first remain = 4 characters: "1219". No leading zeros. Return "1219".

Monotonic Stack — Building the Smallest Number in One Pass — Watch how digits are pushed onto the stack to build the result, and popped when a smaller digit arrives that would produce a better (smaller) number.

Algorithm

  1. Compute remain = len(num) − k (the number of digits to keep)
  2. Initialize an empty stack
  3. For each digit d in num:
    • While k > 0 AND stack is not empty AND stack.top() > d:
      • Pop from stack (remove the larger digit)
      • Decrement k
    • Push d onto stack
  4. Take only the first remain characters from the stack
  5. Strip leading zeros from the result
  6. If the result is empty, return "0"

Code

class Solution {
public:
    string removeKdigits(string num, int k) {
        string stk;
        int remain = num.size() - k;

        for (char c : num) {
            while (k > 0 && !stk.empty() && stk.back() > c) {
                stk.pop_back();
                k--;
            }
            stk.push_back(c);
        }

        // Keep only 'remain' digits
        stk.resize(remain);

        // Strip leading zeros
        int start = 0;
        while (start < (int)stk.size() - 1 && stk[start] == '0') {
            start++;
        }
        return stk.empty() ? "0" : stk.substr(start);
    }
};
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        remain = len(num) - k

        for digit in num:
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)

        # Keep only 'remain' digits, strip leading zeros
        result = ''.join(stack[:remain]).lstrip('0')
        return result if result else '0'
class Solution {
    public String removeKdigits(String num, int k) {
        int remain = num.length() - k;
        StringBuilder stk = new StringBuilder();

        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);
            while (k > 0 && stk.length() > 0 && stk.charAt(stk.length() - 1) > c) {
                stk.deleteCharAt(stk.length() - 1);
                k--;
            }
            stk.append(c);
        }

        // Keep only 'remain' digits
        String result = stk.substring(0, remain);

        // Strip leading zeros
        int start = 0;
        while (start < result.length() - 1 && result.charAt(start) == '0') {
            start++;
        }
        result = result.substring(start);
        return result.isEmpty() ? "0" : result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through each of the n digits exactly once. Each digit is pushed onto the stack once and popped at most once. So the total number of push and pop operations is at most 2n. The final slicing and leading-zero removal are both O(n). Overall: O(n).

Compared to the brute force O(k × n), this is a massive improvement. For n = 10⁵ and k = 5 × 10⁴, the stack approach does roughly 2 × 10⁵ operations instead of 5 × 10⁹.

Space Complexity: O(n)

The stack stores at most n characters (when no digits are removed). The final result string is at most n characters long. Total additional space: O(n).