DEV Community

Subramanya Chakravarthy
Subramanya Chakravarthy

Posted on

2 2

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

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more