⚡Flashcard Drill➔
NeetCode #360LC-402MediumStack
← Back to All Problems

#360 · #402 · Remove K Digits(移掉 K 位数字)

📌 Problem Statement & Constraints

Given a non-negative integer as a string num and an integer k, remove k digits so that the remaining number is the smallest possible, preserving the relative order of the remaining digits. Return the result as a string with no leading zeros (use "0" if the result is empty). Constraints: 1 <= k <= num.length <= 10^5.

💡 Core Algorithmic Approaches

  1. This is the classic "remove digits to minimise" greedy, solved with a monotonically increasing stack.
  2. For each digit, while the stack top is greater than the current digit and removals remain, pop it -- a larger leading digit is always worse.
  3. Push the current digit. If removals remain after the scan, they must come off the end (the number is already non-decreasing).
  4. Finally strip leading zeros; an all-zero result becomes "0".

💻 Benchmark Python3 Implementation

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        st = []
        for d in num:
            # pop larger leading digits while we still have removals
            while k and st and st[-1] > d:
                st.pop()
                k -= 1
            st.append(d)
        if k:                              # number is already non-decreasing
            st = st[:-k]                   # remove from the end
        res = "".join(st).lstrip("0")
        return res if res else "0"

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each digit is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the leftover k: if the digits are already non-decreasing, the removals must come from the end.
  • Using >= in the pop condition: removing equal digits is never beneficial, and it can produce a worse result for the same removal count. Use strict >.
  • Forgetting to strip leading zeros: "10200" with k = 1 gives "200", but "100" with k = 1 gives "00", which must become "0".
  • Returning an empty string: the contract requires "0".
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Stack Problems