Last updated on January 10th, 2025 at 04:57 am

Here, we see a Remove K Digits LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Greedy, Stack

Companies

Google, Snapchat

Level of Question

Medium

Remove K Digits LeetCode Solution

1. 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.

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Monotonic Stack”. This pattern involves maintaining a stack where elements are added or removed based on a specific order (increasing or decreasing). The goal is to efficiently solve problems that require maintaining a sequence of elements in a sorted or partially sorted order.

3. Code Implementation in Different Languages

3.1 Remove K Digits C++

class Solution {
public:
    string removeKdigits(string num, int k) {
        string ans="";
        for(char &c:num)
        {
            while(ans.size() && ans.back()>c &&k)
            {
                ans.pop_back();
                k--;
            }
            if(ans.size()||c!='0')ans.push_back(c);
        }
        while(ans.size()&&k--)
        {
            ans.pop_back();
        }
        return (ans=="")?"0":ans;
    }
};

3.2 Remove K Digits Java

class Solution {
    public String removeKdigits(String num, int k) {
        int len = num.length();
        if(k==len)        
            return "0";
        Stack<Character> stack = new Stack<>();
        int i =0;
        while(i<num.length()){
            while(k>0 && !stack.isEmpty() && stack.peek()>num.charAt(i)){
                stack.pop();
                k--;
            }
            stack.push(num.charAt(i));
            i++;
        }
        while(k>0){
            stack.pop();
            k--;            
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty())
            sb.append(stack.pop());
        sb.reverse();
        while(sb.length()>1 && sb.charAt(0)=='0')
            sb.deleteCharAt(0);
        return sb.toString();
    }
}

3.3 Remove K Digits JavaScript

var removeKdigits = function(num, k) {
    const stack = [];
    let removed = 0;
    for(let n of num) {
        while(stack.length && n < stack[stack.length-1] && removed < k) {
            stack.pop();
            removed += 1;
        }
        stack.push(n);
    }
    while(removed < k) {
        stack.pop();
        removed += 1;
    }
    while(stack.length && stack[0] === '0') {
        stack.shift();
    }
    return stack.length ? stack.join('') : '0';
};

3.4 Remove K Digits Python

class Solution(object):
    def removeKdigits(self, num, k):
        stack = []
        for n in num:
            while( stack and int(stack[-1]) > int(n) and k):
                stack.pop()
                k -= 1
            stack.append(str(n))
        while(k):
            stack.pop()
            k -= 1
        i = 0
        while( i <len(stack) and stack[i] == "0" ):
            i += 1
        return ''.join(stack[i:]) if (len(stack[i:]) > 0) else "0"  

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)