Remove K Digits - Practice Coding Problems

Remove K Digits - Problem

Given a string num representing a non-negative integer and an integer k, return the smallest possible integer after removing k digits from num.

The result should not have leading zeros, except when the result is "0".

Example: If num = "1432219" and k = 3, we can remove digits to get "1219" by removing "4", "3", and "2".

Input & Output

Example 1 — Basic Removal

$ Input: num = "1432219", k = 3

› Output: "1219"

💡 Note: Remove digits 4, 3, and 2 (first occurrence) to get the smallest result. The greedy approach removes larger digits when encountered: 4>3 so remove 4, then 3>2 so remove 3, then 2>2 so remove the first 2.

Example 2 — Leading Zero Handling

$ Input: num = "10200", k = 1

› Output: "200"

💡 Note: Remove the first digit '1' to get '0200', then remove leading zeros to get '200'. This shows the importance of handling leading zeros in the result.

Example 3 — Remove All Same Digits

$ Input: num = "10", k = 2

› Output: "0"

💡 Note: When we need to remove all digits (k >= length), the result should be '0'. This is a special edge case.

Constraints

1 ≤ k ≤ num.length ≤ 10⁵
num consists of only digits
num does not have leading zeros except for num = "0"

Visualization

Tap to expand

Understanding the Visualization

Input

String num and integer k representing digits to remove

Process

Greedily remove larger digits to minimize result

Output

Smallest possible number after removing k digits

Key Takeaway

🎯 Key Insight: Always remove the first digit that's larger than the next digit to minimize the result

Asked in

G Google 35 a Amazon 28 f Facebook 22 A Apple 18

The key insight is to use a greedy approach with a monotonic stack. When processing each digit, remove any larger digits from the stack if we still have removals left. This ensures we build the smallest possible number. Best approach is Greedy Stack with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Monotonic Stack	O(n)	O(n)	Use stack to greedily remove larger digits when building result
Brute Force - Try All Combinations	O(C(n,k) × n)	O(n)	Generate all possible combinations of removing k digits and find minimum

Greedy with Monotonic Stack — Algorithm Steps

Initialize empty stack and removal counter
For each digit, pop larger digits from stack while removals remain
Add current digit to stack
Remove excess digits from end if needed
Handle leading zeros

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Digits

For each digit, remove larger ones from stack

Stack State

Stack maintains increasing order when possible

Final Result

Remove leading zeros and return result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* num, int k) {
    int n = strlen(num);
    char* stack = malloc(n + 1);
    int top = -1;
    int toRemove = k;
    
    for (int i = 0; i < n; i++) {
        char digit = num[i];
        // Remove larger digits from stack while we can
        while (top >= 0 && stack[top] > digit && toRemove > 0) {
            top--;
            toRemove--;
        }
        stack[++top] = digit;
    }
    
    // Remove remaining digits from end if needed
    top -= toRemove;
    stack[top + 1] = '\0';
    
    // Handle leading zeros
    int start = 0;
    while (start <= top && stack[start] == '0') start++;
    
    if (start > top) {
        strcpy(stack, "0");
    } else {
        memmove(stack, stack + start, top - start + 2);
    }
    
    return stack;
}

int main() {
    char num[10001];
    int k;
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    scanf("%d", &k);
    
    char* result = solution(num, k);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each digit is pushed and popped at most once from the stack

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n digits in worst case

⚡ Linearithmic Space

125.0K Views

High Frequency

~25 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Monotonic Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler