Remove K Digits Problem using Stack

Remove K Digits Problem using Stack

The Remove K Digits problem involves removing K digits from a given number represented as a string to obtain the smallest possible number. This can be efficiently solved using a stack to keep track of the digits and ensure the smallest number is formed.

---

Step-by-Step Process

Consider a number represented by the string:

"1432219"

To remove K digits to form the smallest possible number using a stack, follow these steps:

1. Initialize an Empty Stack: Use a stack to keep track of the digits to form the smallest number.
2. Traverse the String: Iterate through each digit in the string.
3. Remove Larger Digits: For each digit, if the stack is not empty and the current digit is smaller than the digit at the top of the stack, pop the stack to remove the larger digit. Continue this process until K digits are removed or the stack is empty.
4. Push Current Digit: Push the current digit onto the stack.
5. Handle Remaining Digits: If there are still digits to be removed after processing all digits in the string, remove them from the end of the stack.
6. Build Result: Construct the result from the digits remaining in the stack. Remove any leading zeros.

After performing these steps, the smallest possible number will be formed.

Input: "1432219", K = 3
Output: "1219"

---

Pseudo Code

Function remove_k_digits(num, k):
    # Initialize an empty stack
    stack = []
    # Traverse the string
    For digit in num:
        # Remove larger digits
        While stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1
        # Push current digit
        stack.append(digit)
    # Handle remaining digits
    While k > 0:
        stack.pop()
        k -= 1
    # Build the result and remove leading zeros
    result = ''.join(stack).lstrip('0')
    # Return the result or '0' if the result is empty
    Return result or '0'

---

Python Program to Solve the Remove K Digits Problem Using Stack

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        return len(self.stack) == 0

    def traverse(self):
        for item in reversed(self.stack):
            print(item, end=" -> ")
        print("None")

# Function to remove K digits to form the smallest possible number
def remove_k_digits(num, k):
    stack = Stack()
    for digit in num:
        while not stack.is_empty() and k > 0 and stack.peek() > digit:
            stack.pop()
            k -= 1
        stack.push(digit)
    while k > 0:
        stack.pop()
        k -= 1
    result = ''.join(stack.stack).lstrip('0')
    return result or '0'

# Example usage:
num = "1432219"
k = 3
print(f"Input number: {num}")  # Output: Input number: 1432219
print(f"Number of digits to remove: {k}")  # Output: Number of digits to remove: 3
smallest_number = remove_k_digits(num, k)
print(f"Smallest possible number: {smallest_number}")  # Output: Smallest possible number: 1219

This Python program defines a stack with methods for pushing, popping, peeking, checking if the stack is empty, and traversing the stack. The remove_k_digits function uses the stack to remove K digits from the input number to form the smallest possible number by processing each digit and updating the stack accordingly.