402. Remove K Digits - Explanation

Problem Link



1. Brute Force

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        num = list(num)
        while k:
            i = 1
            while i < len(num) and num[i] >= num[i - 1]:
                i += 1
            num.pop(i - 1)
            k -= 1

        i = 0
        while i < len(num) and num[i] == '0':
            i += 1

        num = num[i:]
        return ''.join(num) if num else '0'

Time & Space Complexity

  • Time complexity: O(nk)O(n * k)
  • Space complexity: O(1)O(1) or O(n)O(n) depending on the language.

2. Greedy + Stack

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        for c in num:
            while k > 0 and stack and stack[-1] > c:
                k -= 1
                stack.pop()
            stack.append(c)

        while stack and k:
            stack.pop()
            k -= 1

        i = 0
        while i < len(stack) and stack[i] == '0':
            i += 1

        res = stack[i:]
        return ''.join(res) if res else "0"

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Two Pointers

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        l = 0
        num = list(num)

        for r in range(len(num)):
            while l > 0 and k > 0 and num[l - 1] > num[r]:
                l -= 1
                k -= 1
            num[l] = num[r]
            l += 1

        l -= k
        i = 0
        while i < l and num[i] == '0':
            i += 1
        res = ''.join(num[i:l])
        return res if res else '0'

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1) or O(n)O(n) depending on the language.