Remove K Digits Problem – Greedy Stack Approach to Find the Smallest Number

Introduction

The "Remove K Digits" problem is a classic greedy algorithm and monotonic stack interview question. Given a number represented as a string and an integer k, the goal is to remove exactly k digits so that the resulting number is as small as possible.

The relative order of the remaining digits must remain unchanged. Additionally, the final result should not contain leading zeros, and if all digits are removed, the function should return "0".

This problem demonstrates how a greedy strategy combined with a stack-like data structure can efficiently produce the optimal answer in linear time.

Problem Summary

Given:

A number represented as a string s
An integer k

Remove exactly k digits such that:

The resulting number is the smallest possible.
The relative order of the remaining digits remains unchanged.
The result does not contain leading zeros.
If all digits are removed, return "0".

Key Idea

The optimal solution uses a greedy strategy with a stack-like structure.

The intuition is:

Smaller digits should appear earlier in the result.
If a larger digit appears before a smaller digit, removing the larger digit helps minimize the final number.
We maintain a monotonic increasing sequence of digits.

Whenever a smaller digit arrives, we remove larger digits from the end of the current result as long as removals are still available.

Why the Greedy Approach Works

Consider the number:

Suppose we can remove digits.

When we encounter:

4 followed by 3

keeping 4 before 3 makes the number larger.

Removing 4 produces:

which is smaller.

This observation leads to the greedy rule:

Whenever a larger digit appears before a smaller digit, remove the larger digit if removals are still available.

Approach Explained

We iterate through each digit in the string.

Step 1: Maintain a Stack-Like Structure

Use a StringBuilder as a stack to store digits.

Step 2: Remove Larger Previous Digits

While:

k > 0
The stack is not empty
The last digit in the stack is greater than the current digit

remove the last digit.

This helps create the smallest possible prefix.

Step 3: Add Current Digit

Append the current digit to the stack.

Step 4: Remove Remaining Digits

After processing all digits, there may still be removals left.

If:

k > 0

remove digits from the end of the stack.

Step 5: Remove Leading Zeros

Skip all leading zeros in the final result.

Step 6: Handle Empty Result

If the resulting string becomes empty, return:

"0"

Example Walkthrough

Input

s = "1432219"
k = 3

Processing

Read 1

Stack: 1

Read 4

Stack: 14

Read 3

Remove 4 because:

4 > 3

Stack:

Remaining removals:

k = 2

Read 2

Remove 3.

Stack:

Remaining removals:

k = 1

Read 2

Stack: 122

Read 1

Remove last 2.

Stack:

Remaining removals:

k = 0

Continue processing remaining digits.

Final result:

Java Implementation

class Solution {
    public String removeKdig(String s, int k) {
        StringBuilder stack = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            while (k > 0 && stack.length() > 0 &&
                   stack.charAt(stack.length() - 1) > ch) {
                stack.deleteCharAt(stack.length() - 1);
                k--;
            }

            stack.append(ch);
        }

        while (k > 0 && stack.length() > 0) {
            stack.deleteCharAt(stack.length() - 1);
            k--;
        }

        int i = 0;
        while (i < stack.length() && stack.charAt(i) == '0') {
            i++;
        }

        String result = stack.substring(i);

        return result.length() == 0 ? "0" : result;
    }
}

Handling Leading Zeros

Consider:

s = "10200"
k = 1

After removing 1:

Leading zeros should not appear in the answer.

After trimming:

Final output:

"200"

Edge Cases

All Digits Removed

Input:

s = "10"
k = 2

Output:

"0"

Already Increasing Number

Input:

s = "12345"
k = 2

No beneficial removals occur during traversal.

Remove from the end:

Number With Leading Zeros After Removal

Input:

s = "10020"
k = 1

Output:

"20"

Complexity Analysis

Time Complexity

O(n)

Each digit is:

Added to the stack at most once.
Removed from the stack at most once.

Therefore, every character is processed at most twice.

Space Complexity

O(n)

The stack-like structure stores up to n digits.

Why This Solution Is Optimal

The algorithm follows a greedy strategy:

Always remove larger digits that appear before smaller digits.
Build the smallest possible prefix at every step.
Preserve the relative order of remaining digits.

The monotonic increasing structure ensures that every decision contributes to minimizing the final number.

Because each digit is pushed and popped at most once, the solution achieves optimal linear performance.

Conclusion

The Remove K Digits problem is a classic example of combining a greedy strategy with a monotonic stack. By removing larger digits whenever a smaller digit appears later, we ensure that smaller digits occupy more significant positions in the final number.

After processing all digits, any remaining removals are applied from the end, and leading zeros are removed to produce the final answer.

This approach provides an efficient solution with:

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

making it suitable even for very large input strings.