Largest Number - Find out the largest possible number which can be built from N after removing exactly K digits (Easy)

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

ini
N = 3412
K = 1

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

ini
N = 3412
K = 1

Compare adjacent digits:

cpp
3 < 4 → delete 3

Now:

412

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)

sql
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

---

🧪 Edge cases this problem tests

1. Digits already decreasing

   ini
   N = 9876, K = 2 → 98
   

   → Just remove from the end

2. Leading zeros

   ini
   N = 1002, K = 1 → 102
   

3. 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

python
def largest_number_after_k_deletions(N, K):
    digits = list(str(N))
    stack = []

    for d in digits:
        # Remove smaller digits from stack if possible
        while stack and K > 0 and stack[-1] < d:
            stack.pop()
            K -= 1
        stack.append(d)

    # If deletions still remain, remove from the end
    while K > 0:
        stack.pop()
        K -= 1

    # Join digits and remove leading zeros if any
    result = ''.join(stack).lstrip('0')

    return result if result else "0"


# ---- Driver code ----
N, K = map(int, input().split())
print(largest_number_after_k_deletions(N, K))

---

🧠 Step-by-Step Explanation (Layman Friendly)

🔹 Convert the number into digits

python
digits = list(str(N))

We treat the number as characters so we can remove digits easily.

---

🔹 Use a stack to build the best number

python
stack = []

The stack keeps digits in descending order, as much as possible.

---

🔹 Main greedy logic

python
while stack and K > 0 and stack[-1] < d:
    stack.pop()
    K -= 1

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

python
while K > 0:
    stack.pop()
    K -= 1

If digits are already decreasing (like 9876), we remove digits from the end.

---

🔹 Clean result

python
result = ''.join(stack).lstrip('0')

Removes leading zeros if they appear.

---

🧪 Example Walkthrough

Input

yaml
3412 1

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.