# Python with Sorting

• 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...

``````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...

• @StefanPochmann We share almost the same "History"

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

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

• @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.

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

• 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`.

• In the case of 49999, accepted in 169ms

``````def lexicalOrder(self, n):
li = list(range(1,n+1))
li = list(map(lambda x: str(x),li))
li = sorted(li)
return list(map(lambda x: int(x),li))
``````

• @nhuthai08 said in Python with Sorting:

In the case of 49999, accepted in 169ms

``````def lexicalOrder(self, n):
li = list(range(1,n+1))
li = list(map(lambda x: str(x),li))
li = sorted(li)
return list(map(lambda x: int(x),li))
``````

I submitted it five times, never got accepted. Always exceeded the time limit. And no wonder... you're doing way too much work for no good reason. Here's an improved version:

``````    def lexicalOrder(self, n):
li = range(1, n+1)
li = map(str, li)
li.sort()
return map(int, li)
``````

Still doesn't get accepted, though.

• @ManuelP : It improved running time, but my solution cannot run, because
of MEMORY limit, not TIME limit. I am trying to balance time and memory.

• @nhuthai08 Not sure what you mean now, especially the balancing thing. And as I said, I tried your code five times and it always exceeded the time limit.

• @ManuelP : It promted: "Status: Memory Limit Exceeded", not time limit. As I said, it only works in the case of 49999.

• @nhuthai08 I don't believe that. I don't think you got Memory Limit Exceeded with the code you showed. Maybe with some other code. Like my version of it, which did consistently get Memory Limit Exceeded in my tests.

Not sure what "it only works in the case of 49999" is supposed to mean.

• @ManuelP Oops! My mistake! Sorry so much!

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