Remove K Digits

LeetCode 402 | Difficulty: Medium

Medium

Problem Description

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^5`

- `num` consists of only digits.

- `num` does not have any leading zeros except for the zero itself.

Topics: String, Stack, Greedy, Monotonic Stack

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 92 ms)

Metric	Value
Runtime	92 ms
Memory	25.3 MB
Date	2020-03-09

Solution

public class Solution {
    public string RemoveKdigits(string num, int k) {
            Stack<int> s = new Stack<int>();
    int i = 0;
    while (i < num.Length)
    {
        while (k > 0 && s.Count != 0 && s.Peek() > (num[i]-'0'))
        {
            s.Pop();
            k--;
        }
        s.Push(num[i]-'0');
        i++;
    }
    while(k>0)
    {
        s.Pop();
        k--;
    }
    StringBuilder result = new StringBuilder();
    while (s.Count != 0)
    {
        result.Append(s.Pop());
    }
    
    //remove last zeroes
    while(result.Length!=0)
    {
        if(result[result.Length-1]=='0') result.Remove(result.Length-1,1);
        else break;
    }
    if(result.Length==0) result.Append("0");
    return new string(result.ToString().Reverse().ToArray());
    }
}

📜 1 more C# submission(s)

Submission (2020-03-09) — 156 ms, 27.4 MB

public class Solution {
    public string RemoveKdigits(string num, int k) {
        LinkedList<int> s = new LinkedList<int>();
    int i = 0;
    while (i < num.Length)
    {
        while (k > 0 && s.Count != 0 && s.Last() > (num[i] - '0'))
        {
            s.RemoveLast();
            k--;
        }
        s.AddLast(num[i] - '0');
        i++;
    }
    while (k > 0)
    {
        s.RemoveLast();
        k--;
    }
    
    
    while(s.Count!=0 && s.First()==0) s.RemoveFirst();
    if(s.Count == 0) s.AddFirst(0);
    return string.Join("",s);
    }
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?