DEV Community 👩‍💻👨‍💻

Subramanya Chakravarthy
Subramanya Chakravarthy

Posted on

Remove K Digits - LeetCode

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Observation 1: We need to select the first k digits which is most significant as least possible.

Consider this example "191" and k = 1

As we go throught "191"

  1. 91 -> min = 91, "1" is removed
  2. 11 -> min = 11, "9" is removed
  3. 19 -> min = 11, "1" is removed

Here 9 is the most significant digit which means, if any digit less than 9 will make the whole number lesser

In order to solve this kinnd of problem you can think of greedy algorithm

Greedy algorithm is a technique used whenever an optimal solution is required(i.e, min or max)

Here, we need the smallest number possible

Let's see the algorithm

  1. Create a stack to hold the numbers
  2. Loop through each element in the num string
  3. while stack length > 0 && k > 0 && stack[stack.length - 1] > num[i]
  4. Pop the elements in the stack and decrease k by 1
  5. Push each elem to the stack
  6. After coming out of for loop, if k > 0 pop k times from stack
  7. Now remove any leading 0's from the stack
  8. Now convert the stack to string and return it
  9. There is a edge case when there is "0", it might return empty string, handle it

Let's consider few examples of different scenarios

Case 1:

num = "1432219" and k = 3

We need to find the best fit for the first 3 digits in num which is smallest possible. i.e, 143 should be replaced with smallest fit as they are most significant

Steps:

  1. stack = [1], k = 3
  2. stack = [1, 4], k = 3
  3. stack = [1, 4, 3], k = 3
  4. stack = [1, 4], k = 2 as 3 > 2
  5. stack = [1], k = 1 as 4 > 2
  6. stack = [1, 2], k = 1
  7. stack = [1, 2, 2], k = 1
  8. stack = [1, 2], k = 0 as 2 > 1
  9. stack = [1, 2, 1]
  10. stack = [1, 2, 1, 9]

Here's the code

var removeKdigits = function(num, k) {
    let stack = new Array();

    for(let i = 0; i < num.length; i++) {

        while(stack.length > 0 && k > 0 && stack[stack.length - 1] > num[i]) {
            stack.pop();
            k--;
        }

        stack.push(num[i])
    }

    while(k > 0) {
        stack.pop();
        k--;
    }

    let res = stack.join('');
    while(res.charAt(0) === '0') {
        res = res.slice(1);
    }

    if(res.length == 0) {
        return "0";
    }
    return res;
};

Top comments (0)

We are hiring! Do you want to be our Senior Platform Engineer? Are you capable of chipping in across sysadmin, ops, and site reliability work, while supporting the open source stack that runs DEV and other communities?

This role might just be for you!

Apply now