Concise Java Code achieved O(k) in best case and O(k^2) in worse case


  • 0
    M

    Think it in a different way. Instead of removing the k digits, we think about how to pick the remaining digits. If the length of the num string is 7, and we need to remove 3 from it, so it will remain 4 digits.
    So the question is: what is the first remaining digits we should pick from the num string?
    The answer is the minimum digit(assume its index is 2) in the range of [0, 3]. Why? Because we have to pick one from these range, if we don't pick anyone in this range, then the length of remaining digits is less than 4. (This is pretty much like the pigeonhole theory).
    So what about the second remaining digit?
    The same logic, it is the minimum digit in the range of [2+1, 4]. For the following remaining digit, do the same iteration.

    Here is the code:

    public class Solution {
        public String removeKdigits(String num, int k) {
            int len = num.length();
            int remain = len - k; // the number of digits remained after removing k digits
            StringBuilder sb = new StringBuilder();
            int left = -1; // the left index of current search range
            while (remain > 0) {
                int right = len - remain; // the right index of current search range
                char min = '9' + 1;
                for (int i = left+1; i <= right; ++i) {
                    if (num.charAt(i) < min) {
                        min = num.charAt(i);
                        left = i; // update the left index for the next iteration
                    }
                }
                if (sb.length() != 0 || min != '0') sb.append(min); // If it is a leading zero, ignore it
                remain --; 
            }
            if (sb.length() == 0) return "0";
            else return sb.toString();
        }
    }
    

    For the best case, for example [7,6,5,4,3,2,1], the runtime will be O(k), and for the worse case, for example [1,2,3,4,5,6,7], the runtime will be O(k^2). Correct me if I am wrong.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.