402. Remove K Digits

Problem Description

This LeetCode problem asks you to find the smallest possible integer after removing exactly k digits from a string num that represents a non-negative integer. The goal is to reduce the size of the number while keeping the remaining digits in the same order as they were in the original number.

Intuition

The intuition behind the solution is to use a greedy algorithm. If we want the resulting number to be the smallest possible, we should ensure that the higher place values (like tens, hundreds etc.) have the smallest possible digits. Therefore, while parsing the string from left to right, if we encounter a digit that is larger than the digit following it, we remove the larger digit (which is at a higher place value). This decision is greedy because it makes the best choice at each step, aiming to keep the smallest digits at higher place values.

To efficiently perform removals and keep track of the digits, a stack is an excellent choice. Each time we add a new digit to the stack, we compare it to the element on top of the stack (which represents the previous digit in the number). If the new digit is smaller, it means we can make the number smaller by popping the larger digit off the stack. This process is repeated up to k times as required by the problem statement.

The stack represents the digits of the resulting number with the smallest digits at the bottom (higher place values). When k removals are done, or the string is fully parsed, we take the bottom n - k digits from the stack (where n is the length of num), since k digits have been removed, and that forms our result. Leading zeroes are removed as they do not affect the value of the number. If all digits are removed, we must return '0', which is the smallest non-negative integer.

Learn more about Stack, Greedy and Monotonic Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Solution Approach

The implementation of this algorithm is straightforward once you understand the intuition:

We create an empty list called stk, which we will use as a stack to keep track of the valid digits of the smallest number we are constructing.
We need to retain len(num) - k digits to form the new number after we have removed k digits. The variable remain holds this value.
We iterate over each character c in the string num:
- While we still have more digits k to remove, and the stack stk is not empty, and the digit at the top of the stack stk[-1] is greater than the current digit c, we pop the top of the stack. This is because keeping c, which is smaller, will yield a smaller number.
- We also decrement k by 1 each time we pop a digit off the stack since that counts as one removal.
- After the check (and potential removal), we append the current digit c to the stack. This digit is now part of the new number.
After we finish iterating over num, the stack contains the digits of the resulting number, but it might have more digits than necessary if we didn’t need to remove k digits. Thus, we slice the stack up to remain digits.
Next, we need to convert the list of digits into a string. We join the digits in stk up to the remain index and then we remove any leading zeros with .lstrip('0').
The last step is to handle the case where all digits are removed, resulting in an empty string. If that happens, we return '0' because we must return a valid number and 0 is the smallest non-negative integer. In any other case, we return the joined string of digits that now represents the smallest possible integer after the removal of k digits.

This algorithm makes use of a stack, which is a classic data structure that operates on a Last In, First Out (LIFO) principle. It's an ideal choice to store the digits of the new number because it allows for easy removal of the last added digit when a smaller digit comes next. The process is greedy and makes local optimum choices by preferring smaller digits in the higher place values.

Remember, in Python, a list can act as a stack with the append method to push elements onto the stack and the pop method to remove the top element of the stack.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]dp[i] = dp[i - 1] + 1dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]dp[i] = dp[i - 1]

I don’t know

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose the input string num is "1432219" and k is 3. We want to remove 3 digits to make the number as small as possible.

Here's the step-by-step process:

Initialize an empty list stk to represent the stack. The number of digits we want to remain in the final number is remain = len(num) - k = 7 - 3 = 4.
Iterate over each digit in "1432219":
- Start with the first digit '1'. Since the stack is empty, we add '1' to stk.
- Next is '4'. '4' is greater than '1', so we keep it and push '4' to stk.
- Then comes '3'. '3' is smaller than '4' and k > 0, so we pop '4' out of the stack. Now stk = ['1'] and k = 2.
- Now we have '2'. '2' is smaller than '3', so we pop '3'. Now, stk = ['1'] and k = 1.
- Add '2' to the stack. stk = ['1', '2'].
- Another '2' comes, which is the same as the last digit, so we push '2' to stk. stk = ['1', '2', '2'].
- Finally, '1' is smaller than '2', so we pop the last '2' from stk. stk = ['1', '2'], and k = 0 (no more removals allowed).
- Since we've already removed 3 digits, just push '1' and then '9' to the stack. Now, stk = ['1', '2', '1', '9'].
We've finished processing each digit and our stack stk represents the smallest number we could make. However, we need to make sure we have the right number of digits, which should be remain = 4. Since stk already contains 4 digits, there's no need to slice.
Join the stack to form a number and strip leading zeros (if any). result = ''.join(stk).lstrip('0'). In this case, '1219'.
We return '1219', which is the smallest number possible after removing 3 digits from "1432219".

This example illustrates how the stack helps efficiently manage the digits of the new number, ensuring that smaller digits remain at the higher place values whenever possible.

Solution Implementation

1class Solution:
2    def removeKdigits(self, num: str, k: int) -> str:
3        # Initialize a stack to keep track of the digits
4        stack = []
5      
6        # Number of digits to remain in the final number
7        remaining_digits_count = len(num) - k
8      
9        # Iterate over each character in the input string
10        for digit in num:
11            # While we can still remove digits, and the stack is not empty,
12            # and the current digit is smaller than the last digit in the stack:
13            while k and stack and stack[-1] > digit:
14                # Remove the last digit from the stack as it's greater than the current one
15                stack.pop()
16                # Decrease the count of digits we can remove
17                k -= 1
18            # Add the current digit to the stack
19            stack.append(digit)
20      
21        # Build the final number string from the stack up to the remaining digits
22        final_number = ''.join(stack[:remaining_digits_count])
23      
24        # Strip leading zeros from the final number and return it, or return '0' if empty
25        return final_number.lstrip('0') or '0'
26

1class Solution {
2    public String removeKdigits(String num, int k) {
3        // Create a StringBuilder to use as a stack to keep track of digits.
4        StringBuilder stack = new StringBuilder();
5      
6        // Iterate through each character in the input string.
7        for (char digit : num.toCharArray()) {
8            // While the current digit is smaller than the last digit in the stack
9            // and we still have digits to remove (k > 0), remove the last digit.
10            while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > digit) {
11                stack.deleteCharAt(stack.length() - 1);
12                k--;
13            }
14            // Append the current digit to the stack (StringBuilder).
15            stack.append(digit);
16        }
17      
18        // If after the iteration we still need to remove more digits, remove from the end.
19        while (k > 0) {
20            stack.deleteCharAt(stack.length() - 1);
21            k--;
22        }
23      
24        // Remove leading zeros by finding the index of the first non-zero digit.
25        int nonZeroIndex = 0;
26        while (nonZeroIndex < stack.length() && stack.charAt(nonZeroIndex) == '0') {
27            nonZeroIndex++;
28        }
29        // Create a new string starting from the first non-zero digit.
30        String result = stack.substring(nonZeroIndex);
31      
32        // If the resulting string is empty, return "0" instead; otherwise, return the string.
33        return result.isEmpty() ? "0" : result;
34    }
35}
36

1class Solution {
2public:
3    // Function to remove 'k' digits from the string 'num' to get the smallest possible number.
4    string removeKdigits(string num, int k) {
5        string stack; // Using 'stack' to store the characters representing the smallest number
6
7        // Iterate through each character in the input number
8        for (char& digit : num) {
9            // Check if the current digit is smaller than the last digit in 'stack'
10            // and whether we have still digits to remove
11            while (k > 0 && !stack.empty() && stack.back() > digit) {
12                stack.pop_back(); // Remove the last digit from 'stack' to maintain the smallest number
13                --k; // Decrement the count of digits to remove
14            }
15            stack += digit; // Add the current digit to 'stack'
16        }
17
18        // Further remove digits from the end if we haven't removed enough 'k' digits
19        // This is necessary when the sequence was initially increasing
20        while (k > 0) {
21            stack.pop_back(); // Remove the last digit from 'stack'
22            --k; // Decrement the count of digits to remove
23        }
24
25        // Remove leading zeros from the 'stack'
26        int startIndex = 0; // Index to keep track of leading zeros
27        while (startIndex < stack.size() && stack[startIndex] == '0') {
28            ++startIndex; // Increment index to skip the leading zero
29        }
30      
31        string result = stack.substr(startIndex); // Extract the non-zero starting substring as result
32        return result.empty() ? "0" : result; // If result is empty, return "0"; otherwise, return the result
33    }
34};
35

1function removeKdigits(numString: string, k: number): string {
2    // Convert the string to an array of characters for easier manipulation
3    let digitArray = [...numString];
4
5    // Keep removing digits until we have removed k digits
6    while (k > 0) {
7        let indexToDelete = 0; // Initialize deletion index
8
9        // Find where the digit is greater than the one following it; that's our deletion target
10        while (indexToDelete < digitArray.length - 1 && digitArray[indexToDelete + 1] >= digitArray[indexToDelete]) {
11            indexToDelete++;
12        }
13
14        // Remove the digit at the identified deletion index
15        digitArray.splice(indexToDelete, 1);
16
17        // Decrement the count of digits we still need to remove
18        k--;
19    }
20
21    // Join the array back into a string and strip leading zeroes, if any
22    let result = digitArray.join('').replace(/^0*/g, '');
23
24    // If the result is an empty string, return '0', otherwise return the processed number string
25    return result || '0';
26}
27

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed based on the operations performed. The code iterates over each character in the string num which has a length of n. In the worst case, each character may be pushed to and popped from the stack stk once. Pushing and popping from the stack are O(1) operations, but since the inner while loop could run up to k times for each character, it might appear at first as if the complexity is O(nk). However, each element is pushed and popped at most once, resulting in a time complexity of O(n) overall because the while loop can't execute more than n times over the course of the entire function.

Therefore, the total time complexity of the algorithm is:

1O(n)

Space Complexity

The space complexity is determined by the space used by the stack stk, which in the worst case could contain all characters if k is zero or if all characters are in increasing order. Therefore, the space complexity is proportional to the length of the input string num.

Thus, the space complexity of the algorithm is:

1O(n)

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

402. Remove K Digits

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings