DSA interview question

Remove K Digits

Medium · Data structures · Topics: stack, greedy, string

The problem

A coupon system shows a number to the user and lets them delete exactly k digits to get the smallest possible number, keeping the remaining digits in order. Greedy thinking gives the answer: a number is smaller when its leftmost digits are smaller, so whenever a digit is followed by a smaller one, deleting the bigger digit before it always helps. A stack keeps the kept digits in non-decreasing order, popping bigger digits while deletions remain. Leftover deletions come off the end, and leading zeros are stripped.

Example: num = "1432219", k = 3 → "1219".

Function signature

string removeKdigits(const string& num, int k);  // 0 <= k <= num.length()

Test cases

Input `(num, k)`	Output	Explanation
`("1432219", 3)`	`"1219"`	Remove 4, 3 and 2
`("10200", 1)`	`"200"`	Remove 1; leading zeros are dropped
`("10", 2)`	`"0"`	Nothing left means "0"
`("112", 1)`	`"11"`	Non-decreasing: remove from the end
`("123456", 3)`	`"123"`
`("9", 1)`	`"0"`

(Confirm: num has no leading zeros unless it is "0"; the result has no leading zeros; an empty result is "0".)

How interviewers phrase it

"Given a string num representing a non-negative integer and an integer k, return the smallest possible integer after removing k digits" (LeetCode 402).

Clarifying questions to ask

Must the remaining digits stay in order? (Yes.)
How should leading zeros be handled? (Strip them; an empty result is "0".)
How long can num be? (Up to 10⁵, so O(n).)

Follow-ups to expect

"Why is removing a 'peak' digit optimal?"
"Why a stack?"
"What if deletions remain after the scan?"
"Why can the stack be a string?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview