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.

Description Solution Video 15:29

402. Remove K Digits

Medium37.7% acceptance21 companies

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

Asked at top 20 of 21 companies

Park Snapchat PhonePe Coupang

Deloitte Zeta Adobe Walmart Labs Josh Technology Zopsmart

Google Bytedance

+8 more

Amazon Microsoft Meta Bloomberg Tiktok Zoho Accenture Snowflake

Topics

15:29

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

402. Remove K Digits

Asked at top 20 of 21 companies

Topics

Similar problems