402. Remove K Digits LeetCode Solution

In this guide, you will get 402. Remove K Digits LeetCode Solution with the best time and space complexity. The solution to Remove K Digits problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Remove K Digits solution in C++
Remove K Digits solution in Java
Remove K Digits solution in Python
Additional Resources

402. Remove K Digits LeetCode Solution image

Problem Statement of Remove K Digits

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

402. Remove K Digits LeetCode Solution in C++

class Solution {
 public:
  string removeKdigits(string num, int k) {
    if (num.length() == k)
      return "0";

    string ans;
    vector<char> stack;

    for (int i = 0; i < num.length(); ++i) {
      while (k > 0 && !stack.empty() && stack.back() > num[i]) {
        stack.pop_back();
        --k;
      }
      stack.push_back(num[i]);
    }

    while (k-- > 0)
      stack.pop_back();

    for (const char c : stack) {
      if (c == '0' && ans.empty())
        continue;
      ans += c;
    }

    return ans.empty() ? "0" : ans;
  }
};
/* code provided by PROGIEZ */

402. Remove K Digits LeetCode Solution in Java

class Solution {
  public String removeKdigits(String num, int k) {
    if (num.length() == k)
      return "0";

    StringBuilder sb = new StringBuilder();
    LinkedList<Character> stack = new LinkedList<>();

    for (int i = 0; i < num.length(); ++i) {
      while (k > 0 && !stack.isEmpty() && stack.getLast() > num.charAt(i)) {
        stack.pollLast();
        --k;
      }
      stack.addLast(num.charAt(i));
    }

    while (k-- > 0)
      stack.pollLast();

    for (final char c : stack) {
      if (c == '0' && sb.length() == 0)
        continue;
      sb.append(c);
    }

    return sb.length() == 0 ? "0" : sb.toString();
  }
}
// code provided by PROGIEZ

402. Remove K Digits LeetCode Solution in Python

class Solution:
  def removeKdigits(self, num: str, k: int) -> str:
    if len(num) == k:
      return '0'

    ans = []
    stack = []

    for i, digit in enumerate(num):
      while k > 0 and stack and stack[-1] > digit:
        stack.pop()
        k -= 1
      stack.append(digit)

    for _ in range(k):
      stack.pop()

    for c in stack:
      if c == '0' and not ans:
        continue
      ans.append(c)

    return ''.join(ans) if ans else '0'
 # code by PROGIEZ