The explanation is here https://www.youtube.com/watch?v=3QJzHqNAEXs
class Stack<T> {
var array:[T] = [T]()
func push(_ item: T) {
array.append(item)
}
func pop() -> T {
return array.removeLast()
}
func isEmpty() -> Bool {
return array.isEmpty
}
func top() -> T? {
return array.last
}
func display() -> [T] {
print(array)
return array
}
}
class SmallestInteger {
static func removeKdigits(_ num: String, _ k: Int) -> String {
var kNumbersToRemove = k
let stack:Stack<Int> = Stack<Int>()
var numbers:[Int] = num.compactMap { char in
char.wholeNumberValue
}
for number in numbers {
while (!stack.isEmpty() && kNumbersToRemove > 0 && stack.top()! > number) {
stack.pop()
kNumbersToRemove -= 1
}
if !stack.isEmpty() || number != 0 {
stack.push(number)
}
}
// this logic is to handle numbers like 1001, k=2
while !stack.isEmpty() && kNumbersToRemove > 0 {
kNumbersToRemove -= 1
stack.pop()
}
if stack.isEmpty() {
return "0"
}
var stringArray = stack.display().map { number in
String(number)
}
return stringArray.joined()
}
}
print(SmallestInteger.removeKdigits("1432219", 3))
We use a stack here to store the values. If the previous number is greater than the current number, we will remove the previous number. Else store the number in the stack.
Leave a Reply