Greedy approach using Deque, O(n) time and O(n) space


  • 0
    L

    Approach #1: Greedy [Accepted]

    Intuition and Algorithm

    The idea is transforming the problem to pick c = (length - k) characters from input num instead of removing k digits. For the step i, we need to pick the minimum digit in [lastIdx + 1, length - c + i] greedily, where 0 <= i < c.

    public String removeKdigits(String num, int k) {
        StringBuilder builder = new StringBuilder();
        int len = num.length();
        int count = len - k;
        int lastIdx = -1;
        for (int i = 0; i < count; i++) {
            // find the minimum digit in [lastIdx + 1, len - c + i]
            int min = num.charAt(lastIdx + 1) - '0';
            int minIdx = lastIdx + 1;
            for (int j = lastIdx + 2; j <= len - count + i; j++) {
                int cur = num.charAt(j) - '0';
                if (cur < min) {
                    min = cur;
                    minIdx = j;
                }
            }
            lastIdx = minIdx;
            
            if (min != 0 || builder.length() > 0) {
                builder.append("" + min);
            }
        }
        
        return (builder.length() == 0) ? "0" : builder.toString();
    }
    

    Complexity Analysis

    • Time Complexity: O(N^2) where N is the length of input num in the worst case.
    • Space Complexity: O(N) where N is the length of input num.

    Approach #2: Greedy with Deque [Accepted]

    Intuition and Algorithm

    The minimum digit between [lastIdx + 1, length - c + i] can be optimized using a Deque data structure. In the deque, we can keep track a monotonically increasing sequence we got between [lastIdx + 1, length - c + i].

    public String removeKdigits(String num, int k) {
        StringBuilder builder = new StringBuilder();
        int len = num.length();
        int count = len - k;
        int lastIdx = -1;
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < count; i++) {
            while (lastIdx + 1 <= len - count + i) {
                int cur = num.charAt(lastIdx + 1) - '0';
                while (q.size() > 0 && q.getLast() > cur) {
                    q.pollLast();
                }
                
                q.offerLast(cur);
                lastIdx++;
            }
            
            // the minimum digit in [lastIdx + 1, len - c + i]
            int min = q.pollFirst();
            if (min != 0 || builder.length() > 0) {
                builder.append("" + min);
            }
        }
        
        return (builder.length() == 0) ? "0" : builder.toString();
    }
    

    Complexity Analysis

    • Time Complexity: O(N) where N is the length of input num since we access each digit only once.
    • Space Complexity: O(N) where N is the length of input num.

Log in to reply
 

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