Given an integer N which has D digits. You have to delete exactly K digits in integer N. Find out the largest possible number which can be built from N after removing exactly K digits. Input Format: First line contains two space separated integers: N K Output Format: Print the largest possible number which can be built from after removing exactly digits. Constraints: Sample Input 3412 1 Sample Output 412 Time Limit: 1 Memory Limit: 256 Source Limit: Explanation After removing exactly 1 digit, we can make 412 312 342 341 Among, them 412 is the largest possible number.
Solution:
Couple of intuitive questions to ask yourself before jumping to code:
1. What is the power of 10 that will remain from the original number after removing K digits?
Ans: D - K
2. What is the position and value of the largest digit in the remaining number?
Ans: The largest digit must be in the first D - K digits of the original number.
If largest digit is not in the first D - K digits, we go for the second largest digit.
Psuedo Code
Initialize empty stack
For each digit in N:
While stack not empty AND
last digit in stack < current digit AND
deletions remaining:
pop stack
decrease K
push current digit to stack
If deletions still left:
remove last K digits from stack
Answer = digits in stack joined together
My Code
Q: Explain the solution to this problem in layman terms. Give clear descriptions of what this problem is trying to teach/assess, what design pattern, what problem solving trick/technique.
Great problem choice ๐ — this is a classic interview + competitive programming problem, and it teaches an important way of thinking.
I’ll explain this in layman terms, then connect it to what it’s testing, the design pattern, and the core trick.
๐ Problem in simple words
You are given:
-
A number N (as digits)
-
A number K (how many digits you must delete)
๐ Your task:
Delete exactly K digits from N
without changing the order of the remaining digits,
so that the resulting number is as large as possible.
Example
Possible results after deleting 1 digit:
-
Remove 3 → 412
-
Remove 4 → 312
-
Remove 1 → 342
-
Remove 2 → 341
✔️ Largest = 412
๐ง Key constraint that matters
You cannot rearrange digits.
You can only delete digits.
This is what makes the problem non-trivial.
๐งฉ How to think about it (layman explanation)
Let’s think like a human looking at the number:
“If I can delete some digits, I want big digits to come as early as possible.”
Because:
-
A bigger digit at the left makes the number larger
-
Later digits matter less
๐ก Core idea (greedy thinking)
Whenever you see:
-
A smaller digit before a bigger digit
-
AND you still have deletions left
๐ Delete the smaller digit
Why?
Because keeping the bigger digit earlier makes the number larger overall.
Example walk-through
Compare adjacent digits:
Now:
No deletions left → stop
✔️ Correct answer
๐งฐ Design Pattern Used
✅ Greedy Algorithm
You make the best local choice at every step:
“If removing this digit makes the number bigger, do it now.”
Greedy works here because:
-
Earlier digits dominate the value of the number
-
Once a digit is fixed, future digits can’t compensate for a bad choice
๐ Implementation Technique
Monotonic Stack
This problem is usually solved using:
-
A stack that keeps digits in decreasing order
-
While:
-
Stack top < current digit
-
AND deletions left
-
Pop the stack (delete digit).
Why a stack?
It helps you:
-
Look back at previous digits
-
Remove them efficiently
-
Maintain the best possible prefix
✏️ Pseudocode (human-readable)
๐งช Edge cases this problem tests
-
Digits already decreasing
→ Just remove from the end
-
Leading zeros
-
K = D
→ Result is empty or 0 (depending on problem definition)
๐ฏ What this problem is really assessing
| Skill | Tested |
|---|---|
| Greedy thinking | ✅ |
| Stack usage | ✅ |
| Digit manipulation | ✅ |
| Order preservation | ✅ |
| Edge-case handling | ✅ |
| Algorithmic intuition | ✅ |
๐ง Big takeaway
To maximize a number, fix the leftmost digits first
by deleting smaller digits when you get the chance.
This idea appears in many problems:
-
Remove K digits
-
Build largest/smallest number
-
Stock span problems
-
Next greater element
๐ Final one-line summary
This problem teaches you how to:
Use greedy decisions + a stack to build the best possible number while deleting digits without changing order.
If you want next:
-
Full Python code
-
Dry-run with more examples
-
Why greedy is provably correct
-
How this compares to brute force
Just tell me ๐
Full Python Code From ChatGPT
Here is the clean, correct, interview-ready Python solution using the greedy + monotonic stack approach we discussed.
This works efficiently even for very large N (up to 10¹⁸).
✅ Full Python Code
๐ง Step-by-Step Explanation (Layman Friendly)
๐น Convert the number into digits
We treat the number as characters so we can remove digits easily.
๐น Use a stack to build the best number
The stack keeps digits in descending order, as much as possible.
๐น Main greedy logic
This means:
-
If the previous digit is smaller than the current digit
-
AND we still have deletions left
-
Remove the smaller digit to make the number bigger
๐น Handle leftover deletions
If digits are already decreasing (like 9876), we remove digits from the end.
๐น Clean result
Removes leading zeros if they appear.
๐งช Example Walkthrough
Input
Stack evolution
| Step | Digit | Stack | K |
|---|---|---|---|
| 1 | 3 | [3] | 1 |
| 2 | 4 | [] → [4] | 0 |
| 3 | 1 | [4,1] | 0 |
| 4 | 2 | [4,1,2] | 0 |
✔️ Output: 412
⏱️ Time & Space Complexity
| Metric | Value |
|---|---|
| Time | O(D) |
| Space | O(D) |
Where D = number of digits in N.
๐ฏ Why this solution is optimal
-
No brute force
-
No recursion
-
No permutations
-
Works for large numbers
-
Industry-standard greedy solution
๐งฉ What this problem teaches
-
Greedy decision making
-
Monotonic stacks
-
Digit-level manipulation
-
Why earlier digits matter more
If you want next:
-
A brute-force validator
-
Handling
K > 3 -
Explanation of why greedy always works
-
Similar problems to practice
Just say ๐
What is the greedy algorithm in 100 words?
A greedy algorithm is a problem-solving approach where, at each step, you make the best immediate (locally optimal) choice with the hope that these choices lead to an overall optimal solution. It does not look ahead or reconsider past decisions. Greedy algorithms work well when a problem has the greedy-choice property, meaning a locally optimal choice is also globally optimal. They are usually simple, fast, and memory-efficient. Common examples include activity selection, coin change (with certain coin systems), shortest path algorithms like Dijkstra, and problems involving monotonic stacks such as removing digits to form the largest number.






