Python O(k^2) solution


  • 0
    N

    The observation is that the smallest number among the first k + 1 characters has to be included in the solution. You can basically leverage this idea repeatedly. Every time when you find a smallest number among the next k+1 characters, you can discard all the numbers on the left of that character.

        def removeKdigits(self, num, k):
            def helper(index, k, prefix):
                #print index, k, prefix
                if k is 0:
                    return prefix + num[index:]
                if len(num) - index == k:
                    return prefix
                mini = index
                for i in xrange(index, index+k+1):
                    if num[i] < num[mini]:
                        mini = i
                return helper(mini+1, k - (mini - index), prefix + num[mini])
                
            result = helper(0, k, "").lstrip("0")
            return result if result else "0"
    

  • 0
    C

    @newman2 It's not O(k^2). It's O(kn).


  • 0

    @cslns I think it's not even O(kn). Consider inputs like num = 'a' * n with fixed k = 1. With O(kn), this would be O(n). But it goes through the whole string and at every single character the prefix + num[mini] takes Θ(len(prefix)) time and space. And the space adds up as well, because each recursion level holds on to its prefix.

    I think it's only something like O(n ⋅ max(n, k)) time and O(n2) space.


  • 0
    C

    @StefanPochmann recursion is a bad idea as I mentioned in my post: https://discuss.leetcode.com/topic/59985/python-recursive-and-iterative-solutions

    Yes, recursion takes a lot of space for a long string and a large k value.

    The worst case is to scan the whole string for each step. So should it be O(kn)? k is a variable not a constant here. It can be as large as n. Of course, if k = n we just return '0'. But for @newman2 's solution, we need to scan n times if all the characters in num is same like: num='1111111111', k = 10.

    So I say it is O(kn) not O(n), or more precisely should be O(min(k,n) * n) not max(k,n).


  • 0

    @cslns No, as explained it isn't O(kn). And it isn't O(min(k,n) * n), either, for the same reason.


Log in to reply
 

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