Language Selection
Choose your preferred programming language
Showing: Python
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 <= 10^5
- num consists of only digits.
- num does not have any leading zeros except for the zero itself.
Approach 1: Greedy with Stack
Algorithm
- Use a stack to maintain digits in increasing order
- For each digit, remove previous digits that are larger
- Continue until we’ve removed k digits
- Handle remaining digits and leading zeros
Solution
Python:
def removeKdigits(num, k):
"""
Greedy approach using stack
Time: O(n) - each digit pushed and popped at most once
Space: O(n) - stack storage
"""
if k >= len(num):
return "0"
stack = []
for digit in num:
# Remove digits that are larger than current digit
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# Remove remaining k digits from the end
while k > 0:
stack.pop()
k -= 1
# Remove leading zeros
result = ''.join(stack).lstrip('0')
return result if result else "0"
Java:
class Solution {
/**
* Greedy approach using stack
* Time: O(n) - each digit pushed and popped at most once
* Space: O(n) - stack storage
*/
public String removeKdigits(String num, int k) {
if (k >= num.length()) {
return "0";
}
Stack<Character> stack = new Stack<>();
for (char digit : num.toCharArray()) {
// Remove digits that are larger than current digit
while (k > 0 && !stack.isEmpty() && stack.peek() > digit) {
stack.pop();
k--;
}
stack.push(digit);
}
// Remove remaining k digits from the end
while (k > 0) {
stack.pop();
k--;
}
// Build result and remove leading zeros
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
result.append(stack.pop());
}
result.reverse();
// Remove leading zeros
while (result.length() > 1 && result.charAt(0) == '0') {
result.deleteCharAt(0);
}
return result.toString();
}
}
Go:
// removeKdigits - Greedy approach using stack
// Time: O(n) - each digit pushed and popped at most once
// Space: O(n) - stack storage
func removeKdigits(num string, k int) string {
if k >= len(num) {
return "0"
}
var stack []byte
for i := 0; i < len(num); i++ {
digit := num[i]
// Remove digits that are larger than current digit
for k > 0 && len(stack) > 0 && stack[len(stack)-1] > digit {
stack = stack[:len(stack)-1]
k--
}
stack = append(stack, digit)
}
// Remove remaining k digits from the end
for k > 0 {
stack = stack[:len(stack)-1]
k--
}
// Remove leading zeros
result := string(stack)
for len(result) > 1 && result[0] == '0' {
result = result[1:]
}
if result == "" {
return "0"
}
return result
}
JavaScript:
/**
* Greedy approach using stack
* Time: O(n) - each digit pushed and popped at most once
* Space: O(n) - stack storage
*/
function removeKdigits(num, k) {
if (k >= num.length) {
return "0";
}
const stack = [];
for (let i = 0; i < num.length; i++) {
const digit = num[i];
// Remove digits that are larger than current digit
while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
stack.pop();
k--;
}
stack.push(digit);
}
// Remove remaining k digits from the end
while (k > 0) {
stack.pop();
k--;
}
// Remove leading zeros
let result = stack.join('').replace(/^0+/, '');
return result || "0";
}
C#:
public class Solution {
/// <summary>
/// Greedy approach using stack
/// Time: O(n) - each digit pushed and popped at most once
/// Space: O(n) - stack storage
/// </summary>
public string RemoveKdigits(string num, int k) {
if (k >= num.Length) {
return "0";
}
var stack = new Stack<char>();
foreach (char digit in num) {
// Remove digits that are larger than current digit
while (k > 0 && stack.Count > 0 && stack.Peek() > digit) {
stack.Pop();
k--;
}
stack.Push(digit);
}
// Remove remaining k digits from the end
while (k > 0) {
stack.Pop();
k--;
}
// Build result and remove leading zeros
var result = new StringBuilder();
while (stack.Count > 0) {
result.Append(stack.Pop());
}
var resultStr = new string(result.ToString().Reverse().ToArray());
// Remove leading zeros
while (resultStr.Length > 1 && resultStr[0] == '0') {
resultStr = resultStr.Substring(1);
}
return resultStr;
}
}
Approach 2: Two Pointers
Algorithm
- Use two pointers to find the best position to remove digits
- Keep track of the smallest number formed so far
- Remove digits greedily from left to right
Solution
Python:
def removeKdigits(num, k):
"""
Two pointers approach
Time: O(n * k) - in worst case
Space: O(1) - constant extra space
"""
if k >= len(num):
return "0"
result = num
for _ in range(k):
if not result:
return "0"
# Find the first position where result[i] > result[i+1]
i = 0
while i < len(result) - 1 and result[i] <= result[i + 1]:
i += 1
# Remove the digit at position i
result = result[:i] + result[i + 1:]
# Remove leading zeros
result = result.lstrip('0')
return result if result else "0"
Java:
class Solution {
/**
* Two pointers approach
* Time: O(n * k) - in worst case
* Space: O(1) - constant extra space
*/
public String removeKdigits(String num, int k) {
if (k >= num.length()) {
return "0";
}
StringBuilder result = new StringBuilder(num);
for (int remove = 0; remove < k; remove++) {
if (result.length() == 0) {
return "0";
}
// Find the first position where result[i] > result[i+1]
int i = 0;
while (i < result.length() - 1 && result.charAt(i) <= result.charAt(i + 1)) {
i++;
}
// Remove the digit at position i
result.deleteCharAt(i);
}
// Remove leading zeros
while (result.length() > 1 && result.charAt(0) == '0') {
result.deleteCharAt(0);
}
return result.toString();
}
}
Go:
// removeKdigits - Two pointers approach
// Time: O(n * k) - in worst case
// Space: O(1) - constant extra space
func removeKdigits(num string, k int) string {
if k >= len(num) {
return "0"
}
result := []byte(num)
for remove := 0; remove < k; remove++ {
if len(result) == 0 {
return "0"
}
// Find the first position where result[i] > result[i+1]
i := 0
for i < len(result)-1 && result[i] <= result[i+1] {
i++
}
// Remove the digit at position i
result = append(result[:i], result[i+1:]...)
}
// Remove leading zeros
for len(result) > 1 && result[0] == '0' {
result = result[1:]
}
if len(result) == 0 {
return "0"
}
return string(result)
}
JavaScript:
/**
* Two pointers approach
* Time: O(n * k) - in worst case
* Space: O(1) - constant extra space
*/
function removeKdigits(num, k) {
if (k >= num.length) {
return "0";
}
let result = num;
for (let remove = 0; remove < k; remove++) {
if (result.length === 0) {
return "0";
}
// Find the first position where result[i] > result[i+1]
let i = 0;
while (i < result.length - 1 && result[i] <= result[i + 1]) {
i++;
}
// Remove the digit at position i
result = result.slice(0, i) + result.slice(i + 1);
}
// Remove leading zeros
result = result.replace(/^0+/, '');
return result || "0";
}
C#:
public class Solution {
/// <summary>
/// Two pointers approach
/// Time: O(n * k) - in worst case
/// Space: O(1) - constant extra space
/// </summary>
public string RemoveKdigits(string num, int k) {
if (k >= num.Length) {
return "0";
}
var result = new StringBuilder(num);
for (int remove = 0; remove < k; remove++) {
if (result.Length == 0) {
return "0";
}
// Find the first position where result[i] > result[i+1]
int i = 0;
while (i < result.Length - 1 && result[i] <= result[i + 1]) {
i++;
}
// Remove the digit at position i
result.Remove(i, 1);
}
// Remove leading zeros
while (result.Length > 1 && result[0] == '0') {
result.Remove(0, 1);
}
return result.ToString();
}
}
Key Insights
- Greedy Strategy: Always remove the leftmost digit that is larger than the next digit
- Monotonic Stack: Use stack to maintain digits in increasing order
- Leading Zeros: Handle leading zeros in the final result
- Edge Cases: Handle cases where k >= length of number
Edge Cases
- k >= length: Return “0”
- Leading Zeros: Remove leading zeros from result
- All Same Digits: Remove from the end
- Single Digit: Handle single digit numbers
Follow-up Questions
- Remove K Digits to Make Largest: Modify to find the largest number
- Remove K Digits with Constraints: Add constraints on which digits can be removed
- Multiple Operations: Allow both removal and addition operations
- Range Queries: Handle multiple queries efficiently
Common Mistakes
- Not handling leading zeros: Forgetting to remove leading zeros
- Wrong greedy strategy: Not removing the correct digits
- Edge case handling: Not handling k >= length case
- String manipulation: Inefficient string operations