Build Lowest Number by Removing n digits from a given number. Given a string ‘str’ of digits and an integer ‘n’, build the lowest possible number by removing ‘n’ digits from the string and not changing the order of input digits. The idea is to remove local-maxima, scanning left->right, in initial K - N digits (K=total digits); such that the sequ…

LowestNumberRemovingNdigits.java

import java.util.LinkedList;
import java.util.ListIterator;

/**
 * Created by Abhishek on 31-Oct-17.
 * <p>
 * http://www.geeksforgeeks.org/build-lowest-number-by-removing-n-digits-from-a-given-number/
 * <p>
 * Build Lowest Number by Removing n digits from a given number
 * 4
 * Given a string ‘str’ of digits and an integer ‘n’, build the lowest possible number by removing ‘n’ digits from the string and not changing the order of input digits.
 * <p>
 * Examples:
 * <p>
 * Input: str = "4325043", n = 3
 * Output: "2043"
 * <p>
 * Input: str = "765028321", n = 5
 * Output: "0221"
 * <p>
 * Input: str = "121198", n = 2
 * Output: "1118"
 * <p>
 */

public class LowestNumberRemovingNdigits {

    /**
     * Flag to switch use of findSmallestNumberUtil() implementations
     */
    private static final boolean USE_OPTIMIZATION = true;

    /**
     * Non optimized version. Uses typical indexing mechanism for better understanding of the logic.
     *
     * @param digits A LinkedList of all the individual digits in the input
     * @param remove no. of digits to be removed
     */
    private static void findSmallestNumberUtil(LinkedList<Integer> digits, int remove) {

        int i = 0;
        int remaining = remove;
        while (i < digits.size() - remaining && remaining > 0) {
            if (digits.get(i) > digits.get(i + 1)) { // if current > next: remove current
                digits.remove(i);
                remaining--;
                if (i > 0) { // check 'previous' with 'next' in the next iteration
                    i--;    // keep removing until all previous digits are less than next digit; or cannot remove more since "remaining == 0"
                }
            } else { // move to next index
                i++;
            }
        }
        while (remaining > 0) { // remove all remaining trailing digits
            if (digits.isEmpty()) {
                throw new IllegalStateException("Cannot remove more elements than present in the string");
            }
            digits.remove(i);
            remaining--;
        }
    }

    /**
     * Iterator version. Optimization in getting i_th element of a link list. In non iterator
     * version, every get(i) and remove(i) call need linear traversal to the i_th element, which
     * is not the case with this iterator implementation.
     * <p>
     * NOTE: Read ListIterator documentation for better understanding of the steps.
     * https://docs.oracle.com/javase/7/docs/api/java/util/ListIterator.html
     *
     * @param digitsList A LinkedList of all the individual digits in the input
     * @param remove     no. of digits to be removed
     */
    private static void findSmallestNumberUtil2(LinkedList<Integer> digitsList, int remove) {

        int remaining = remove;
        ListIterator<Integer> dig = digitsList.listIterator();
        Integer current, next;

        current = dig.next(); // initializing current
        while (remaining > 0 && dig.nextIndex() <= digitsList.size() - remaining) {
            if (current > (next = dig.next())) {    // cursor after 'next'
                dig.previous(); // Take a step back. Now cursor between current and next

                // Keep removing all previous elements which are bigger than 'next', until remaining > 0
                while (remaining > 0 && dig.hasPrevious() && dig.previous() > next) {  // Cursor before 'current', if true.
                    dig.remove(); // 'current' removed.
                    remaining--;
                    // cursor between 'previous' and 'next'.
                }
                current = dig.next(); // initialization for next iteration, moving cursor after 'next'
            } else {
                current = next; // initialization for next iteration, cursor is already after 'next'.
            }

        }
        // removing all trailing 'remaining' digits. Cursor is already after next; can directly call remove().
        while (remaining > 0) {
            dig.remove();
            remaining--;
            if (dig.hasNext()) {
                dig.next(); // necessary before next call of remove();
            }
        }
    }

    public static int findSmallestNumber(int input, int remove) {
        LinkedList<Integer> digits = new LinkedList<>();

        // deconstruct input into individual digits
        int number = input;
        while (number > 0) {
            digits.addFirst(number % 10);
            number /= 10;
        }
        // Illegal argument check
        if (remove > digits.size()) {
            return -1;
        }

        // compute result
        if (USE_OPTIMIZATION) {
            findSmallestNumberUtil2(digits, remove);
        } else {
            findSmallestNumberUtil(digits, remove);
        }

        // reconstruct output int
        for (int digit : digits) {
            number = number * 10 + digit;
        }

        return number;
    }

    public static String findSmallestNumber(String number, int remove) {
        // Illegal argument check
        if (remove > number.length()) {
            return "";
        }

        // deconstruct input into individual digits
        LinkedList<Integer> digits = new LinkedList<>();
        for (int i = 0; i < number.length(); i++) {
            digits.add(number.charAt(i) - '0');
        }

        // compute result
        if (USE_OPTIMIZATION) {
            findSmallestNumberUtil2(digits, remove);
        } else {
            findSmallestNumberUtil(digits, remove);
        }

        // reconstruct output int
        StringBuilder finalStr = new StringBuilder();
        for (int digit : digits) {
            finalStr.append(digit);
        }
        return finalStr.toString();
    }

    public static void main(String args[]) {
        System.out.println(findSmallestNumber("4325043", 3));
        System.out.println(findSmallestNumber("765028321", 5));
        System.out.println(findSmallestNumber("765028321", 7));
        System.out.println(findSmallestNumber(121198, 2));
        System.out.println(findSmallestNumber("124456457", 3));
        System.out.println(findSmallestNumber("124456457", 9));
        System.out.println(findSmallestNumber(124456457, 9));
    }
}