Skip to main content
Talentd

Remove K Digits - Solution & Explanation

MediumStringStackGreedyMonotonic Stack11 min readAsked at: Amazon, Microsoft, Meta +18
Practice this problem

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:

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 <= 105
  • num consists of only digits.
  • num does not have any leading zeros except for the zero itself.

Approach Overview

Problem Overview: You receive a numeric string num and an integer k. Remove exactly k digits so the resulting number is as small as possible while preserving the relative order of the remaining digits. Leading zeros must be handled carefully, and if all digits are removed the result should be "0".

Approach 1: Brute Force Digit Removal (Exponential time, O(2^n) time, O(n) space)

The naive strategy explores all ways to remove k digits and keeps the smallest resulting number. You recursively choose whether to remove or keep each digit until exactly k removals are made. After constructing each candidate string, normalize leading zeros and compare it against the current minimum. This approach demonstrates the core goal of minimizing the number but quickly becomes impractical because the number of combinations grows exponentially. It only works for very small inputs and mainly serves as a conceptual baseline.

Approach 2: Greedy Monotonic Stack (Optimal) (O(n) time, O(n) space)

The optimal strategy uses a greedy rule: remove digits that create a larger prefix. If a digit is bigger than the next one, deleting it makes the number smaller. A monotonic stack captures this idea efficiently. Iterate through the digits of num. While the stack is not empty, the current digit is smaller than the top of the stack, and you still have removals left (k > 0), pop the stack. This removes a larger digit that would otherwise increase the final number.

Push each processed digit onto the stack. After the scan, if k removals remain, remove digits from the end since the suffix is the largest remaining portion. Finally, build the result string from the stack and trim leading zeros. If the string becomes empty, return "0". The stack effectively maintains digits in increasing order, making this a classic combination of greedy, stack, and string processing techniques.

Recommended for interviews: Interviewers expect the monotonic stack solution. It shows you recognize the greedy property: removing a larger digit before a smaller one always improves the number. The brute force idea proves you understand the objective, but the stack-based O(n) solution demonstrates strong algorithmic thinking and familiarity with monotonic data structures.

Approach 1: Monotonic Stack Approach

This approach uses a stack to build the smallest possible number. We iterate over each digit in the string, and for each digit, we compare it with the top of the stack (if the stack is not empty). If the current digit is smaller than the top of the stack and we still have digits to remove, we pop from the stack. Finally, after the loop, if there are remaining digits to remove, we simply remove them from the end of the constructed stack. This ensures the smallest possible arrangement of the remaining digits.

This Python implementation utilizes a stack to keep track of the most desirable sequence of digits. As the function iterates over each digit, it determines whether the stack should pop any elements based on whether doing so would create a smaller number. After the loop, any remaining digits are removed by slicing off the end of the stack. Leading zeros are removed from the final result, and if this leads to an empty string, we return '0'.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of digits in num, because each digit is processed at most twice (once pushed and once popped).
Space Complexity: O(n), because of the space required for the stack to hold the digits.

Try this approach in the editor →

Approach 2: Greedy Algorithm

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Monotonic Stack Approach

Time Complexity: O(n), where n is the number of digits in num, because each digit is processed at most twice (once pushed and once popped).
Space Complexity: O(n), because of the space required for the stack to hold the digits.

Greedy Algorithm—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Digit RemovalO(2^n)O(n)Conceptual understanding or very small inputs
Greedy Monotonic StackO(n)O(n)Optimal approach for large inputs and interview settings

Video Solution

L14. Remove K Digits | Stack and Queue Playlist • take U forward • 158,154 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Remove K Digits easy or hard?
Remove K Digits is rated Medium on LeetCode. The implementation is straightforward once you recognize the greedy rule and apply a monotonic stack, but identifying that insight can be challenging for beginners.
Remove K Digits Python/Java solution
Most implementations follow the same monotonic stack pattern. Use a list as a stack in Python or a Deque/StringBuilder in Java, pop while the previous digit is larger than the current one and k is positive, then build the result while removing leading zeros.
How to solve Remove K Digits in O(n)?
Traverse the number from left to right while maintaining a stack of digits. While the stack top is larger than the current digit and k is still positive, pop the stack to remove the larger digit. Push the current digit, and after traversal remove remaining digits from the end if k > 0, then strip leading zeros.
What is the best approach for Remove K Digits?
The optimal solution uses a greedy monotonic stack. Iterate through the digits and remove previous digits while the current digit is smaller and removals are still allowed. This guarantees the smallest possible prefix and runs in O(n) time with O(n) space.
Is Remove K Digits asked at Google/Amazon/Meta?
Remove K Digits is a common greedy and monotonic stack interview problem and has appeared in coding interviews at companies like Amazon, Google, and other large tech firms. It tests your ability to identify greedy choices and implement stack-based optimization.
What data structure is used in Remove K Digits?
The primary data structure is a stack used in a monotonic increasing manner. The stack helps efficiently remove previously chosen digits when a smaller digit appears, ensuring the smallest possible number is constructed.
What is the time complexity of Remove K Digits?
The optimal monotonic stack solution runs in O(n) time where n is the number of digits in the string. Each digit is pushed and popped from the stack at most once. Space complexity is O(n) for the stack storing the resulting digits.

Ready to solve this problem?

Practice Remove K Digits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Append K Integers With Minimal Sum

Next

Create Maximum Number