Be the first user to complete this post

  • 0
 Add to List
Hard

398. Smallest Number after Removing K digits

Objective: Given a number with N digits, write a program to get the smallest number possible after removing k digits from number N.

OR

Implement a method that returns the lowest possible number that could be generated after removing n characters from a string of digits.

Example:

N = 1453287, k = 3
Output: 1287

N = 4321, k=2
Output: 21

N = 22222, k=3
Output: 22

Approach: Use Stack

  • Iterate through the given number from left to right, one digit at a time.
  • while k> && stack is not empty and top element in the stack is greater than current digit
    • If yes then, pop out the top element from the stack.
    • Reduce the k by 1.
  • Push the current digit to stack.
  • while k is greater than 0.
    • pop-out elements from the stack.
    • Reduce the k by 1
  • Pull all the digits from the stack and construct the number and reverse it, this will be the final answer. (if there are 0 at the start of the answer, remove those).
  • See the code below for more understanding.

Output:

Input: 1453287, k: 3
Smallest number after removing 3 digits: 1287

Reference: Here

Related Problems: