Remove K Digits - LeetCode

#stack #greedy

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"

91 -> min = 91, "1" is removed
11 -> min = 11, "9" is removed
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

Create a stack to hold the numbers
Loop through each element in the num string
while stack length > 0 && k > 0 && stack[stack.length - 1] > num[i]
Pop the elements in the stack and decrease k by 1
Push each elem to the stack
After coming out of for loop, if k > 0 pop k times from stack
Now remove any leading 0's from the stack
Now convert the stack to string and return it
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:

stack = [1], k = 3
stack = [1, 4], k = 3
stack = [1, 4, 3], k = 3
stack = [1, 4], k = 2 as 3 > 2
stack = [1], k = 1 as 4 > 2
stack = [1, 2], k = 1
stack = [1, 2, 2], k = 1
stack = [1, 2], k = 0 as 2 > 1
stack = [1, 2, 1]
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;
};