**Solution**

**Remove K Digits** https://leetcode.com/problems/remove-k-digits/

**General Concept**

- Examples which are interesting: "1234567", "7654321". The first is strictly increasing and the second is strictly decreasing.
- How do you choose to remove the first element?
- You will scan from left to right and remove the first peak element. Example 1 that would be 7, the last element. Example 2 that would be 7, the first

element. - Why the first peak element? You want to remove the first largest element from left which has a smaller element on right, so that the smaller element can fill in for the large element that we removed.

**Brute Force**

- You will repeat this process k times and have a complexity of O(K * N). https://discuss.leetcode.com/topic/59871/two-algorithms-with-detailed-explaination

**Stack Simulation**

- Now how can we do the above efficiently? We can use a stack to simulate this.
- if x > st[-1], push x. If x < st[-1], pop all elements from the stack which are greater than x while making sure we do not pop more than a total of k elements.
- Adjust for boundary conditions.

```
class Solution(object):
def removeKdigits(self, num, k):
"""
:type num: str
:type k: int
:rtype: str
"""
st, required = [], k
for x in num:
while required and st and st[-1] > x:
st.pop()
required = required-1
st.append(x)
result = "".join(st[0:len(num)-k]).lstrip("0")
return result if len(result) else "0"
```