Workspace

Problem workspace

3 day streakD

Remove K Digits

MediumStacksSimulation & greedy

The challenge

Remove exactly k digits from a decimal string to produce the smallest possible number as a string.

Nonempty decimal string without leading zeros except 0 itself. 0 ≤ k ≤ n. Normalize leading zeros and return 0 if empty.

Example

1432219, k = 3 → 1219.

Use the walkthrough below to inspect the input and each state change.

See Remove K Digits, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyk = 3
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.10413223241596Main stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 12

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: ["1","4","3","2","2","1","9"] · k = 3

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

While deletions remain and top > current, remove the top digit.

Indices are zero-based. C++ uses C++17 or later.

def solve(values, k):
    stack = []
    for digit in values:
        while k and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    if k: del stack[-k:]
    return ''.join(stack).lstrip('0') or '0'

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap