Crack the Backend

Problem Statement

You are given a string num representing a non-negative integer, and an integer k. Remove k digits from num so that the remaining digits form the smallest possible number. You must not produce leading zeros (the result may be "0" if that is the only possibility). Return the result as a string (no leading zeros).

Key Observations

Greedy (monotonic stack): We want to keep the result lexicographically smallest. While we have removals left, we should remove a digit when the next digit is smaller (so the number gets smaller). So we maintain a stack of digits in non-decreasing order: when the current digit is smaller than the stack top, popping the top is "removing" that digit — do it while k > 0 and stack not empty and stack.peek() > digit. Then push the current digit. After one pass, if k > 0, remove the last k digits (they are the largest). Trim leading zeros.

Approach

High-level: Stack of characters (digits). For each digit: while k>0 and stack not empty and stack.peek() > digit, pop and k--; push digit. If k>0, pop k times. Build string from stack, remove leading zeros; if empty return "0".

Steps: Deque<Character> st; for (char c : num.toCharArray()) { while (k>0 && !st.isEmpty() && st.peek()>c) { st.pop(); k--; } st.push(c); } while (k-->0) st.pop(); build string, trim zeros.

Implementation

Java

public String removeKdigits(String num, int k) {
    Deque<Character> st = new ArrayDeque<>();

    for (char c : num.toCharArray()) {
        while (k > 0 && !st.isEmpty() && st.peek() > c) { st.pop(); k--; }
        st.push(c);
    }

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

    StringBuilder sb = new StringBuilder();

    while (!st.isEmpty()) {
        sb.append(st.pop());
    }

    sb.reverse();

    while (sb.length() > 1 && sb.charAt(0) == '0') {
        sb.deleteCharAt(0);
    }

    return sb.length() == 0 ? "0" : sb.toString();
}

Test Cases

Example 1

Input

num = "1432219", k = 3

Expected

"1219"

Explanation

Remove 4,3,2.

Complexity Analysis

Time: O(n).
Space: O(n) for stack.

Follow-ups

Previous smaller; range queries.