Python with Sorting


  • 14

    Three accepted solutions and me rambling on about failed attempts :-D


    Solution 1 (accepted in 1792, 1747, 1700 ms)

    I just sort the numbers 1 to n using my custom comparison. To compare two numbers, I "left-shift" them both before comparing them. For example if n = 49999, then I left-shift numbers so they're five digits. That is, 42 becomes 42000 and 123 becomes 12300. In case of ties, e.g., 420 also becoming 42000, the stability of sorted keeps them in order.

    def lexicalOrder(self, n):
        top = 1
        while top * 10 <= n:
            top *= 10
        def mycmp(a, b, top=top):
            while a < top: a *= 10
            while b < top: b *= 10
            return -1 if a < b else b < a
        return sorted(xrange(1, n+1), mycmp)
    

    Solution 2 (accepted in 1268, 1508, 1320, 1356, 1336 ms)

    def lexicalOrder(self, n):
        withKeys = []
        for i in xrange(1, n+1):
            key = i
            while key < 1000000:
                key *= 10
            withKeys.append(key * 10000000 + i)
        withKeys.sort()
        return [ki % 10000000 for ki in withKeys]
    

    Here I combine each number with a left-aligned version of it, for example:

         42  =>  42000000000042
       4200  =>  42000000004200
     123456  =>  12345600123456
    

    Then just sort these and then extract the lower parts.


    Complexity

    I think Time complexity and space complexity are both O(n) (at least if sort does what I think it does, I'll check some more), and the space complexity has a low hidden factor.

    The time and memory limits for Python for this problem are pretty low, requiring a fairly efficient solution. On LeetCode, Python ints are 64 bits, so embedding the left-aligned version of numbers in the numbers (solution 2) doesn't cost extra memory. Also, sorting simple ints is fast. Especially since the order from 1 to n is already largely sorted lexicographically, like the streak from 100 to 999 and the streak from 1000 to 9999. And Python's (Tim)sort can take advantage of those streaks and just merge them. If it merges "left to right" like I think it does, then it merges the small streaks first and only integrates the longest streaks last, which leads to overall O(n) time.


    Optimizing Solution 2 (accepted in 980, 984, 980 ms)

    Instead of assuming that we get numbers up to seven digits long and using constants, this uses the largest power of 10 up to n.

    def lexicalOrder(self, n):
        highDigit = 1
        while highDigit * 10 <= n:
            highDigit *= 10
        higherDigit = highDigit * 10
        withKeys = []
        for i in xrange(1, n+1):
            key = i
            while key < highDigit:
                key *= 10
            withKeys.append(key * higherDigit + i)
        withKeys.sort()
        return [ki % higherDigit for ki in withKeys]
    

    History...

    Of course the first thing I had tried was this:

    def lexicalOrder(self, n):
        return sorted(range(1, n+1), key=str)
    

    Outrageously, this wasn't accepted! Got "Memory Limit Exceeded" at input n=49999! So next I tried the cmp-version of sorted instead of the key-version, and building strings only on the fly so it takes less memory:

    def lexicalOrder(self, n):
        return sorted(range(1, n+1), lambda a, b: cmp(str(a), str(b)))
    

    Horrendously, this wasn't accepted! Got "Time Limit Exceeded" at input n=49999! So next I tried converting to strings, sorting those, and converting back to ints. Uses more memory, but less time:

    def lexicalOrder(self, n):
        return map(int, sorted(map(str, xrange(1, n+1))))
    

    Unfathomably, this wasn't accepted! Got "Memory Limit Exceeded" at input n=49999! The horror! Apparently LeetCode really didn't want me to get away with being lazy. So I tried it without sorting or strings and built the numbers in correct order:

    def lexicalOrder(self, n):
        def dfs(i):
            if i <= n:
                result.append(i)
                for d in xrange(10):
                    dfs(10 * i + d)
        result = []
        for i in range(1, 10):
            dfs(i)
        return result
    

    Irritatingly, this wasn't accepted! Got "Time Limit Exceeded"! At input n=14959! So it was even slower than the above. Geez. And none of this was even remotely close to the "5,000,000" that the problem threatened me with. I gave up. And implemented that last solution in C++. It got accepted.

    Later I found out that the "5,000,000" isn't even close to true, the largest actual test case is 49999. But even after lots of different attempts, I still can't get any simple stringify+sort solution accepted. The most efficient I came up with is this:

    def lexicalOrder(self, n):
        return sorted(xrange(1, n+1), lambda a, b, s=str: 1 if s(b) < s(a) else -1)
    

    That uses xrange, which is faster than range, uses the cmp-version of sorted because the key version gets memory limit exceeded, uses a fast local variable instead of the slower global str, and exploits that there are no duplicate numbers so I just have to distinguish two cases which I do with < instead of the cmp function. Still, after all of that optimization it's not fast enough. But based on comparing it with accepted solutions in custom testing, I think it's close. Maybe 10% too slow.

    I did get one stringify+sort solution accepted, but it's less simple. I'll post that one later...


  • 1
    O

    @StefanPochmann We share almost the same "History"


  • 0

    @StefanPochmann haha same comments here, "outrageous", "horrendous", when I didn't get the sorting solutions accepted!


  • 0
    K

    @StefanPochmann A little tweak can get dfs accepted. Click here to see whether you can explain one thing puzzles me.


  • 0

    @kejin Hmm, after getting it accepted in C++, I did try a few optimizations in the Python one and I don't think any worked. Apparently I didn't try it like that.


  • 1
    D

    @StefanPochmann Love the history. Thanks keep posting more. I like to read about "the process".


  • 0

    The dfs can be accepted by modifying a little bit

    class Solution(object):
    
        def lexicalOrder(self, n):
            result = []
            for i in range(1, 10):
                self.dfs(result, i, n)
            return result
    
        # This solve the memory limit issue
        # I don't understand this though
        # why using closure consume more memory
        def dfs(self, result, i, n):
            if i <= n:
                result.append(i)
                
                # Adding this extra condition check
                # solve the time limit issue 
                # w/o this, when you doing dfs, you need to search one more level
                # and level(k) usually has 10 times more nodes than level(k-1)
                if 10 * i > n: return
                
                for d in xrange(10):
                    self.dfs(result, 10*i+d, n)
    

    The running time is 1038 ms.


Log in to reply
 

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