Java Coding Challenge - Smallest Number After Removing K Digits Using Stack

Introduction

In this coding challenge, the task is to find the smallest possible number that can be obtained after removing exactly k digits from a given number. The order of the digits in the original number must remain the same, and we need to preserve the relative order of the digits.

This problem can be solved efficiently using a stack, which allows us to remove digits based on their comparison with subsequent digits.

Problem Statement

Given a string representation of a number nr and an integer k, remove k digits from the number to form the smallest possible number.

Example:

• Input:

  • nr = "4321"
  • k = 2

• Output:

  • The smallest possible number after removing two digits from 4321 is "21".

Approach

To solve this problem, we use a stack. The stack will help us keep track of the digits while ensuring that the number remains as small as possible after removing k digits.

Key Operations:

1. Traverse the Number: For each digit in the number, we compare it with the top digit in the stack. If the current digit is smaller, we remove the top of the stack (i.e., "pop") because it makes the number smaller by doing so.
2. Remove Extra Digits: After traversing the number, we may still have extra digits to remove (especially when the number has consecutive digits in decreasing order). We handle this by popping the remaining digits from the stack.
3. Handle Leading Zeros: After building the smallest number, the stack may have leading zeros, which we should ignore when constructing the final number.

Java Code Implementation

import java.util.Stack;

public class Numbers {

    // Prevent instantiation
    private Numbers() {
        throw new AssertionError("Cannot be instantiated");
    }

    // Method to find the smallest number after removing k digits
    public static void smallestAfterRemove(String nr, int k) {

        // Handle invalid cases
        if (nr == null || k <= 0 || k >= nr.length()) {
            System.out.println("The number is: " + 0);
            return;
        }

        Stack<Character> stack = new Stack<>();
        int i = 0;

        // Traverse the number string
        while (i < nr.length()) {
            // Remove digits from the stack if they are greater than the current digit
            while (k > 0 && !stack.isEmpty() && stack.peek() > nr.charAt(i)) {
                stack.pop();
                k--;
            }
            // Push the current digit onto the stack
            stack.push(nr.charAt(i));
            i++;
        }

        // If there are still digits left to remove, pop them from the stack
        while (k > 0) {
            stack.pop();
            k--;
        }

        // Print the result from the stack and handle leading zeros
        System.out.println("The number is (as a printed stack; "
                + "ignore leading 0s (if any)): " + stack);
    }
}

Explanation:

1. Input Validation:

   • If the number is null or k is out of valid range, we return 0.
   • Example:

     if (nr == null || k <= 0 || k >= nr.length()) {
         System.out.println("The number is: " + 0);
         return;
     }
     

2. Traversing the Number:

   • We iterate through each character (digit) of the number and push it onto the stack.

   • Before pushing, we compare it with the top of the stack. If the top of the stack is greater than the current digit, we remove (pop) the top of the stack to ensure we get a smaller number.

   • Example of logic for discarding larger digits:

     while (k > 0 && !stack.isEmpty() && stack.peek() > nr.charAt(i)) {
         stack.pop();
         k--;
     }
     stack.push(nr.charAt(i));
     

3. Remove Remaining Digits:

   • After the main loop, if there are still digits to remove (k > 0), we pop from the stack to remove the required number of digits.
   • Example:

     while (k > 0) {
         stack.pop();
         k--;
     }
     

4. Final Output:

   • The digits remaining in the stack represent the smallest possible number. We print the stack, and the user should ignore any leading zeros.

   • Example:

     System.out.println("The number is (as a printed stack; ignore leading 0s (if any)): " + stack);
     

Main Class to Test the Implementation

package coding.challenge;

public class Main {

    public static void main(String[] args) {
        String nr = "4321";

        // Find the smallest number after removing 2 digits
        Numbers.smallestAfterRemove(nr, 2);
    }
}

Example Output:

The number is (as a printed stack; ignore leading 0s (if any)): [2, 1]

Explanation of Output:

• For the input nr = "4321" and k = 2, the method removes the digits 4 and 3, resulting in the smallest possible number "21".

Time Complexity:

• Time Complexity: O(n), where n is the length of the number. Each digit is processed at most twice (once pushed onto the stack, and once popped), leading to linear time complexity.
• Space Complexity: O(n), as the stack can hold at most n digits.

Conclusion

In this coding challenge, we used a stack to solve the problem of finding the smallest number after removing k digits from a given number. The stack-based approach ensures that the number is processed efficiently in O(n) time. This method is commonly used in competitive programming and interviews to demonstrate a strong understanding of stack operations and optimization techniques.