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

• #### 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.

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