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;
};