Remove K Digits

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.

---

✅ 1. Problem Explanation (In Simple Terms)

You're given:

• A non-negative number in string format (e.g., "1432219")

• An integer k = number of digits to remove

Your task:
Remove exactly k digits to make the smallest possible number.

🧠 Return the result as a string with no leading zeros.
If the result is empty → return "0".

---

💡 2. Key Insights

1. We want to remove digits to get the smallest number, which means:

   • We should remove bigger digits when a smaller digit follows them

   • This is a greedy problem — remove left-side peaks

2. Use a monotonic stack:

   • Push digits into the stack

   • Before pushing, pop from the stack while:

     • Top is greater than current digit

     • And we still have k digits to remove

3. After the loop:

   • If k > 0 → remove extra digits from end of stack

   • Join stack to form result, remove leading zeros

---

🧠 3. Steps to Solve

1. Initialize an empty stack = []

2. Iterate over each digit in the input number:

   • While stack is non-empty and top > current digit and k > 0 → pop

   • Push current digit to the stack

3. After iteration, if k > 0 → pop from end of stack k times

4. Build the result from the stack:

   • Join characters

   • Remove leading zeros

   • If empty → return "0"

---

✅ 4. JavaScript Code (Clean & Optimized)

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
function removeKdigits(num, k) {
  const stack = [];

  for (const digit of num) {
    while (stack.length > 0 && k > 0 && stack[stack.length - 1] > digit) {
      stack.pop();
      k--;
    }
    stack.push(digit);
  }

  // If k still > 0, remove from end
  while (k > 0) {
    stack.pop();
    k--;
  }

  // Convert to string and remove leading zeros
  const result = stack.join('').replace(/^0+/, '');
  return result === '' ? '0' : result;
}

---

🔍 5. Dry Run Example

Input:
num = "1432219", k = 3

Step-by-step:
→ Remove '4' → smaller '3' coming
→ Remove '3' → smaller '2' coming
→ Remove '2' → final result: [1, 2, 1, 9]

Stack after cleanup → "1219"

✅ Output: "1219"

Another example:

num = "10200", k = 1

→ Remove '1'? No (it's smallest)
→ Remove '2'? Yes → stack: [0, 0]

✅ Output: "200" → remove leading zeros → "200"

---

⏱️ 6. Time & Space Complexity

• Time Complexity: O(n)
  Each digit is pushed and popped at most once

• Space Complexity: O(n)
  For the stack

---

✅ Final Verdict

• Classic greedy + monotonic stack problem

• Great for showcasing digit manipulation and stack thinking

• Clean, linear time solution with minimal edge case handling