Log inSign up
mediumLeetCodeNot Started

Remove K Digits

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

Problem Statement

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 · Standard Peak Removal:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Removing digits 4, 3, and 2 forms the smallest number 1219.

Example 2 · Leading Zeros Created:

Input: num = "10200", k = 1
Output: "200"
Explanation: Removing 1 yields 0200, which trims to 200.

Example 3 · All Digits Removed:

Input: num = "10", k = 2
Output: "0"
Explanation: Removing all digits results in an empty string, which evaluates to 0.

Constraints:

  • 1 <= k <= num.length <= 105
  • num consists of only digits.
  • num does not have any leading zeros except for the zero itself.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the greedy mathematical choice: replacing a larger digit with a smaller digit at higher place values always minimizes the number.
  • Master stack-based character filtering with trailing deletion and leading zero cleanup.
  • Recognize the monotonic increasing stack pattern for lexicographical optimization.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Iterate through characters of num.
  • While k > 0 and stack is non-empty and currChar < stack.top(), pop stack and decrement k--.
  • Push currChar to stack.
  • If k > 0 after the loop, truncate k elements from the top of the stack.
  • Remove leading zeros from the result string. If empty, return '0'.

Connected Patterns:

Remove Duplicate LettersCreate Maximum NumberSmallest Subsequence of Distinct Characters

1. Iterative Peak Removal

Intuition

Repeatedly find the first digit that is greater than the digit following it, delete that digit, and repeat k times.

Algorithm

  1. Step 1: Repeat k times: find the first index i where num[i] > num[i+1].
  2. Step 2: If no such index exists (digits are non-decreasing), remove the last character.
  3. Step 3: Delete the character at index i.
  4. Step 4: After k removals, strip leading zeros.
  5. Step 5: Return '0' if string is empty, otherwise return the cleaned string.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 std::string removeKdigits(std::string num, int k) {
7 while (k > 0 && !num.empty()) {
8 size_t i = 0;
9 while (i + 1 < num.size() && num[i] <= num[i + 1]) {
10 i++;
11 }
12 num.erase(i, 1);
13 k--;
14 }
15 size_t start = num.find_first_not_of('0');
16 if (start == std::string::npos) return "0";
17 return num.substr(start);
18 }
19};
20
21int main() {
22 Solution solver;
23 std::cout << "Output: " << solver.removeKdigits("1432219", 3) << std::endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(K * N) — In each of the K steps, scan the string to find the first peak (num[i] > num[i+1]) and delete it, shifting string elements.
  • Space complexity: O(N) — O(N) space for intermediate string copies.

Why Brute Force Doesn't Scale:

For N = 100,000 and K = 50,000, naive O(K * N) takes 5 * 109 ops (severe TLE).

Monotonic Stack processes 100,000 digits in a single pass in ~8ms.

2. Vector Stack Simulation

Intuition

Instead of searching for peaks from the beginning on each removal, maintain a vector stack that accumulates digits in non-decreasing order.

Algorithm

  1. Step 1: Iterate each digit ch in num.
  2. Step 2: While k > 0, vector is non-empty, and ch < vector.back(), pop back and decrement k.
  3. Step 3: Push ch to vector.
  4. Step 4: Truncate remaining k elements from back.
  5. Step 5: Format leading zeros.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string removeKdigits(std::string num, int k) {
8 std::vector<char> st;
9 for (char ch : num) {
10 while (!st.empty() && k > 0 && st.back() > ch) {
11 st.pop_back();
12 k--;
13 }
14 st.push_back(ch);
15 }
16 while (k > 0 && !st.empty()) {
17 st.pop_back();
18 k--;
19 }
20 std::string res = "";
21 bool leadingZero = true;
22 for (char ch : st) {
23 if (leadingZero && ch == '0') continue;
24 leadingZero = false;
25 res.push_back(ch);
26 }
27 return res.empty() ? "0" : res;
28 }
29};
30
31int main() {
32 Solution solver;
33 std::cout << "Output: " << solver.removeKdigits("10200", 1) << std::endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N) — Using a vector as a stack allows single-pass push/pop operations.
  • Space complexity: O(N) — O(N) vector space.

3. Optimal In-Place String Monotonic Stack

Intuition

Treat the output string directly as a monotonic stack to avoid intermediate object allocations and perform pop operations directly on the string buffer.

Algorithm

  1. Step 1: Initialize an empty string buffer stack.
  2. Step 2: Loop through each character d in num.
  3. Step 3: While k > 0 and stack is not empty and stack.back() > d, pop from stack and decrement k.
  4. Step 4: Push d to stack.
  5. Step 5: If k > 0, truncate the last k characters.
  6. Step 6: Skip leading zeros and return '0' if string is empty.

Optimal Monotonic Stack Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
Current operationSTEP 1 OF 7
Stack: '1'
Visual state
Values and pointers at this exact step
stack
This stack trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

Stack: 1

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 std::string removeKdigits(std::string num, int k) {
7 std::string st = "";
8 for (char c : num) {
9 while (!st.empty() && k > 0 && st.back() > c) {
10 st.pop_back();
11 k--;
12 }
13 st.push_back(c);
14 }
15 while (k > 0 && !st.empty()) {
16 st.pop_back();
17 k--;
18 }
19 size_t nonZero = st.find_first_not_of('0');
20 if (nonZero == std::string::npos) return "0";
21 return st.substr(nonZero);
22 }
23};
24
25int main() {
26 Solution solver;
27 std::cout << "Output: " << solver.removeKdigits("1432219", 3) << std::endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass with each character pushed and popped at most once. Clean linear runtime.
  • Space complexity: O(N) — O(N) space for building the result string.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Iterative Peak RemovalO(K * N)O(N)Find first peak and delete it K times.Re-scanning and string splicing on each removal.
2.Vector Stack SimulationO(N)O(N)Use dynamic array as stack to maintain increasing digits.Memory copying during array conversion.
3.Optimal In-Place String Monotonic StackOptimalO(N)O(N)Direct string buffer mutation as a monotonic stack.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to trim remaining k digits when input is already sorted (e.g., num = '12345', k = 2).

Pitfall 2:

Returning an empty string "" instead of "0" when all digits become zero.

Pitfall 3:

Using < instead of > when checking for peak removal.

Crucial Edge Cases to Validate:

  • `k == num.length` — All digits are removed; returns '0'.
  • Leading zeros created (e.g. `num = '10200', k = 1`) — Removing 1 leaves 0200, which strips to '200'.
  • Already sorted ascending (e.g. `num = '12345', k = 2`) — Removes from the back to give '123'.
  • All identical digits (e.g. `num = '1111', k = 2`) — Removes trailing digits to give '11'.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the greedy principle clearly: leftmost digits carry the highest weight (most significant place values).
  2. Point out that the problem reduces to maintaining a monotonic increasing stack.
  3. Remember the 3 crucial post-processing steps: (1) truncate remaining k from tail, (2) trim leading zeros, (3) fallback to '0' if string is empty.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we remove digits when stack.top() > currDigit?

2.What must be done if k > 0 after examining all digits in num?

Back to DSA Sheet