LeetCode 402. Remove K Digits in Java

In this post we will solve the LeetCode 402 Remove K Digits problem.

Given string num representing a non-negative integer num, and an integer k, 
return the smallest possible integer after removing k digits from num.

Constraints:

o 1 <= k <= num.length <= 10^5
o num consists of only digits.
o num does not have any leading zeros except for the zero itself.

If interested in this problem I suggest you read the current description in the LeetCode website. The requirements may be refined since this post.

We are given a string `num` of integers and an integer `k` representing the number of integers we must remove from the string in order to get the smallest possible integer. The associated LeetCode website provides a few examples.

It looks like the problem might be solved using a greedy algorithm. To apply it we need to find a condition in which a local problem is solved; that is what needs to be done to return the smallest integer by removing one of k integers from the provided string.

As an example, in the first test case we are given the string “1432219” for we will need to decide which digit to keep when we encounter ‘1’ and ‘4’. Since we want to get the smallest possible value, we would need to discard ‘4’ and keep ‘1’. In the next pass we will compare ‘1’ and ‘3’ and for the same reason, we would keep ‘1’.

For the result to be correct, we need to take into consideration the last two constraints listed in the problem description.

I tend to develop software using a Test-Driven Development approach. For it to work, we need to start with a base approach, and as soon as some unit of code is completed, I like to test it. That way we will not end with a candidate solution riddle with issues. As we visit the code please keep this approach in mind.

We will be developing a set of three solutions of the function of interest. We will be using the Java programming language and the VSCode IDE on a Windows platform. I will be copying the solutions to the IDE provided by LeetCode for final testing and submission.

Due to the approach, we will need to develop a test scaffold. Please note that the test scaffold IS NOT PART OF THE SOLUTION!

    public String removeKdigits(String num, int k) {
    }

The signature for the function of interest takes as arguments a string `num` and an integer `k`. The function returns a string.

In Java strings are immutable objects. Each time we make a change a new string is created. This is quite expensive. Because of this situation, which is not unique to the Java programming language, we will need to use additional data structures. This will become clear when we visit the actual code for the different implementations.

1432219
3
main <<<   nums: 1432219
main <<<      k: 3
main <<< output ==>1219<==
main <<< output ==>1219<==
main <<< output ==>1219<==


10200
1
main <<<   nums: 10200
main <<<      k: 1
main <<< output ==>200<==
main <<< output ==>200<==
main <<< output ==>200<==


10
2
main <<<   nums: 10
main <<<      k: 2
main <<< output ==>0<==
main <<< output ==>0<==
main <<< output ==>0<==


10
1
main <<<   nums: 10
main <<<      k: 1
main <<< output ==>0<==
main <<< output ==>0<==
main <<< output ==>0<==


12300456
3
main <<<   nums: 12300456
main <<<      k: 3
main <<< output ==>456<==
main <<< output ==>456<==
main <<< output ==>456<==


12300456
2
main <<<   nums: 12300456
main <<<      k: 2
main <<< output ==>100456<==
main <<< output ==>100456<==
main <<< output ==>100456<==


112
1
main <<<   nums: 112
main <<<      k: 1
main <<< output ==>11<==
main <<< output ==>11<==
main <<< output ==>11<==


1111111
3
main <<<   nums: 1111111
main <<<      k: 3
main <<< output ==>1111<==
main <<< output ==>1111<==
main <<< output ==>1111<==


12345
1
main <<<   nums: 12345
main <<<      k: 1
main <<< output ==>1234<==
main <<< output ==>1234<==
main <<< output ==>1234<==

We have a set of test cases. Our test code will have to read the first two input lines which provide the values for `num` and ‘k`. Our test code then displays the contents of such variables so we can make sure all is well so far. This is what we need to do as we are developing our solutions using a TDD approach.

Our test code seems to call three implementations of the function of interest. The returned values seem to match the three implementations.

    /**
     * Test scaffold
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read string nums ****
        String nums = br.readLine().trim();

        // **** read int k ****
        int k = Integer.parseInt(br.readLine().trim());

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<<   nums: " + nums);
        System.out.println("main <<<      k: " + k);

        // **** call function of interest and display result ****
        System.out.println("main <<< output ==>" + removeKdigits0(nums, k) + "<==");

        // **** call function of interest and display result ****
        System.out.println("main <<< output ==>" + removeKdigits1(nums, k) + "<==");

        // **** call function of interest and display result ****
        System.out.println("main <<< output ==>" + removeKdigits(nums, k) + "<==");
    }

Our test code reads the two input lines, allocates and populates the two variables which will be used as arguments to the function of interest. The three implementations of the function of interest are called and the result for each invocation is displayed.

To avoid writing a test scaffold, you can always develop the solution on the online IDE provided by LeetCode.

    /**
     * Given string num representing a non-negative integer num, and an integer k, 
     * return the smallest possible integer after removing k digits from num.
     * Using Greedy algorithm with stack and string builder.
     * 
     * 40 / 40 test cases passed.
     * Status: Accepted
     * Runtime: 7 ms
     * Memory Usage: 39.4 MB
     * 
     * Runtime: 7 ms, faster than 70.37% of Java online submissions.
     * Memory Usage: 39.3 MB, less than 71.43% of Java online submissions.
     * 
     * Execution: O(n) - Space: O(2 * n)
     */
    static public String removeKdigits0(String num, int k) {

        // **** sanity checks ****
        int len = num.length();
        if (len == k) return "0";

        // **** initialization ****
        Stack<Character> stack  = new Stack<>();
        StringBuilder sb        = new StringBuilder();

        // **** greedy algorithm - O(n) ****
        for (int i = 0; i < len; i++) {

            // **** for ease of use ****
            char ch = num.charAt(i);

            // **** char in stack > ch in num (greedy selection) - O(k) ****
            while (k > 0 && !stack.isEmpty() && stack.peek() > ch) {
                stack.pop();
                k--;
            }

            // **** push this character into the stack ****
            stack.push(ch);
        }

        // **** remove from stack characters (if needed) - O(k) ****
        for ( ; k > 0; k--) stack.pop();

        // **** copy stack contents to string builder - O(n) ****
        while (!stack.isEmpty()) sb.append(stack.pop());

        // **** reverse string builder ****
        sb.reverse();

        // **** remove leading 0s from string builder - O(n) ****
        while (sb.length() > 1 && sb.charAt(0) == '0') sb.deleteCharAt(0);

        // **** return string ****
        return sb.toString();
    }

We start by performing a sanity check.

We then initialize a stack and a string builder. The stack will be used to keep in order the digits we keep in our implementation of a greedy algorithm. The purpose of the string builder is to optimize string manipulations.

The loop implements our greedy algorithm for two digits at a time. We will be checking the current digit in the `num` string with the top digit in our stack. We will be discarding larger values from the stack in favor of smaller ones in the `num` string. Please make sure the logic matches the implementation of the loop. The rest of the code is needed to deal with the two last constraints and strings.

Back in the code, the next loop removes additional digits from the string (stack). We need to make sure we remove exactly `k` digits from the `num` string.

For ease of use, we copy the stack contents into a string builder. Since a stack has on the top the last digit, we need to reverse the order of digits in the string builder.

Once that is done, we need to make sure we remove any leading 0s before we extract the string from the string builder and return it to the caller.

Please take a look at the comment section of this implementation. Our solution was accepted, but perhaps we could do better!

    /**
     * Given string num representing a non-negative integer num, and an integer k, 
     * return the smallest possible integer after removing k digits from num.
     * Using Greedy algorithm with array and string builder.
     * 
     * 40 / 40 test cases passed.
     * Status: Accepted
     * Runtime: 4 ms
     * Memory Usage: 40.5 MB
     * 
     * Runtime: 4 ms, faster than 95.04% of Java online submissions.
     * Memory Usage: 40.5 MB, less than 26.78% of Java online submissions.
     * 
     * Runtime: O(n) - Space: O(n)
     */
    static public String removeKdigits1(String num, int k) {

        // **** sanity checks ****
        int len = num.length();
        if (len == k) return "0";

        // **** initialization ****
        StringBuilder sb        = new StringBuilder();
        char[] numChars         = num.toCharArray();
        boolean[] flags         = new boolean[len];
        int j                   = 0;

        // **** traverse numChars array (greedy algorithm) - O(n) ****
        for (int i = 0; i < len; i++) {

            // **** for ease of use ****
            char ch = numChars[i];

            // **** check current character ch ****
            while (k > 0 && j >= 0 && numChars[j] > ch) {
                flags[j] = false;
                k--;
                for ( ; j >= 0 && flags[j] == false; j--);
            }

            // **** use this digit ****
            flags[i] = true;

            // **** last digit for future comparison ****
            j = i;
        }

        // **** remove additional characters (k needs to be 0) - O(k) ****
        for ( ; k > 0; k--) {
            flags[j] = false;
            for ( ; j >= 0 && flags[j] == false; j--);  
        }

        // **** populate string builder removing leading 0s - O(n) ****
        boolean start = true;
        for (int i = 0; i < len; i++) {

            // **** skip leading 0s and disable start flag (if needed) ****
            if (start == true) {
                if (flags[i] == true) {
                    if (numChars[i] == '0') continue;
                    else start = false;
                }
            }

            // **** add this character to the string builder ****
            if (flags[i] == true) sb.append(num.charAt(i));
        }

        // **** append 0 to empty string builder (if needed) ****
        if (sb.length() == 0) sb.append('0');

        // **** return string ****
        return sb.toString();
    }

In this second implementation we replace the stack with an array of characters and an array of boolean. We will need to play with indices in the arrays to implement the same greedy approach.

In the loop we select the current digit and compare it with an entry in the `num` string at position `j`. The variable and the contents of the flags array are modified as needed. Please compare this loop with the similar loop in the previous implementation using a stack.

After the loop completes, we need to make sure we have removed the `k` digits from the `num` string.

Now we will populate the string builder with digits from the `num` string when the associated entry in the flags array is set to `true`. In addition we use the `start` boolean to help us remove leading 0s from the resulting string.

At this point we need to make sure our string builder has at least one entry. If it represents an empty string, we need to append “0”.

Finally we return the string representation in the string builder.

Please refer to the comment section of this implementation of the function of interest. It seems we did better, but perhaps we could still shave off some additional time!

    /**
     * Given string num representing a non-negative integer num, and an integer k, 
     * return the smallest possible integer after removing k digits from num.
     * Using Greedy algorithm with array and string builder.
     * 
     * 40 / 40 test cases passed.
     * Status: Accepted
     * Runtime: 2 ms
     * Memory Usage: 39.2 MB
     * 
     * Runtime: 2 ms, faster than 99.70% of Java online submissions.
     * Memory Usage: 39.2 MB, less than 84.50% of Java online submissions.
     *
     * Execution: O(n) - Space: O(2 * n)
     */
    static public String removeKdigits(String num, int k) {

        // **** sanity checks ****
        int len = num.length();
        if (len == k) return "0";

        // **** initialization ****
        StringBuilder sb        = new StringBuilder();
        boolean[] flags         = new boolean[len];
        int j                   = 0;

        // **** greedy algorithm - O(n) ****
        for (int i = 0; i < len; i++) {

            // **** ****
            while (k > 0 && j >= 0 && num.charAt(j) > num.charAt(i)) {
                flags[j] = false;
                k--;
                for ( ; j >= 0 && flags[j] == false; j--);
            }

            // **** use this digit ****
            flags[i] = true;

            // **** last digit for future comparison ****
            j = i;
        }

        // **** remove characters (if needed) - O(k) ****
        for ( ; k > 0; k--) {
            flags[j] = false;
            for ( ; j >= 0 && flags[j] == false; j--);  
        }

        // **** populate string builder ****
        for (int i = 0; i < len; i++)
            if (flags[i] == true) sb.append(num.charAt(i));

        // **** remove leading 0s from string builder ****
        while (sb.length() > 1 && sb.charAt(0) == '0') sb.deleteCharAt(0);

        // **** return string ****
        return sb.toString();
    }

This is the final implementation for this problem. In it we will use a string builder and the flags array. We will eliminate the use of the char array from the previous pass.

As you can see the steps are the same as in the previous two implementations. I do not have much more to add.

Now take a look at the comments section of this implementation. We managed to reduce the execution time in half.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named RemoveKDigits.

Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., Codility_, HackerRank, LeetCode to name a few).

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Enjoy;

John

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.