Stack + Greedy = O(N)


  • 0
    K

    Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

    Note:
    The length of num is less than 10002 and will be ≥ k.
    The given num does not contain any leading zero.

    Example 1:
    Input: num = "1432219", k = 3
    Output: "1219"
    Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

    Example 2:
    Input: num = "10200", k = 1
    Output: "200"
    Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

    Example 3:
    Input: num = "10", k = 2
    Output: "0"
    Explanation: Remove all the digits from the number and it is left with nothing which is 0.

    Idea:
    It is obvious that to make a number smaller we have to make their highest digits smaller.
    Greedy: The most priority task is to make the first digit as small as possible, the second priority is to make second digit as small as possible, etc.
    We need to know the distance from each digit to the next which is smaller.

    Ex:
    num = 1 4 3 2 2 1 9
    dist = [inf, 1, 1, 2, 1, inf, inf]
    Where "inf" means that there no digits after current digit which is smaller than current.

    How can we calculate array dist?
    We can use stack for it.
    If the stack is empty we push current digit.
    If not empty, we pop digits until stack is empty or digit on the top of the stack is smaller than current digit (it means that every digit in stack is smaller than current). When we pop the digit from stack we initialize dist[idx] = current_idx - idx, where idx is an index of the digit we pop, current_idx is an index of current digit.
    After all the operations we have some None values in dist (for digits which are still in stack) it means that distance for that digits should be "inf"

    After that we need to traverse through distance array from first element to last element. We decrease the value of k if dist[current_idx] < k

    Ex:
    num = 1 4 3 2 2 1 9
    dist = [inf, 1, 1, 2, 1, inf, inf]

    • k = 3, idx = 0, inf > k => do nothing
    • k = 3, idx = 1, 1 < k => k = k - 1 = 2 (num[1] will not be in our final num)
    • k = 2, idx = 2, 1 < k => k = k - 1 = 1 (num[2] will not be in our final num)
    • k = 1, idx = 3, 2 > k =>do nothing
    • k = 1, idx = 4, 1 <= k => k = k - 1 = 0 (num[4] will not be in our final num)

    After this operations we have k >= 0.
    If k == 0 we know all the idx of num[idx] which will not be in our final num => delete that digits, return the string
    If k > 0 we have to delete last k digits in num, it is obvious

    At the end we need to handle the cases with leading 0, if we have leading zero in num, we delete it until num[0] != 0 or len(num) != 1.

    Time: O(N)
    Memory: O(N)


Log in to reply
 

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