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.


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


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.

Java Code:


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

Reference: Here

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

%d bloggers like this: