Greedy with stack java O(n)

  • 0

    Greedy approach is to remove i-th digits if it is more than the element which is in position i+1. Just implementing this idea will be O(n*k). To optimize the solution till O(n) we can use stack.

    public class Solution {
        public String removeKdigits(String num, int k) {
            Stack<Character> stack = new Stack<>();
            for (int i=0; i<num.length(); i++) {
                char c = num.charAt(i);
                while (!stack.isEmpty() && stack.peek()>c && k>0) {
            while (k-->0) stack.pop();
            return removeLeadingZeros(stack);
        private String removeLeadingZeros(Stack<Character> stack) {
            StringBuilder ret = new StringBuilder();
            boolean isLeadingZero = true;
            for (int i=0; i<stack.size(); i++) {
                if (stack.get(i)=='0' && isLeadingZero) continue;
                isLeadingZero = false;
            if (ret.toString().isEmpty()) return "0";
            else return ret.toString();

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.