What's the problem of my code? Time Limit Exceeded.


  • 0
    X
    class Solution(object):
        def lexicalOrder(self, n):
            """
            :type n: int
            :rtype: List[int]
            """
            # return map(int, sorted(map(str, range(1,n + 1))))
            # ls = range(1, n + 1)
            # ls.sort(key=str)
            # return ls
            result = []
            k = len(str(n))
            start = int(str(n)[0])
            from collections import deque
            q = deque()
            for i in xrange(1,10):
                q.clear()
                if i < start:
                    q.append(i)
                    while len(q):
                        item = q.pop()
                        result.append(item)
                        if len(str(item)) >= k:
                            continue
                        add_p = [int(str(item)+str(p)) for p in xrange(9,-1,-1)]
                        q.extend(add_p)
                elif i > start:
                    if k == 1:
                        continue
                    q.append(i)
                    while len(q):
                        item = q.pop()
                        result.append(item)
                        if len(str(item)) >= k-1:
                            continue
                        add_p = [int(str(item)+str(p)) for p in xrange(9,-1,-1)]
                        q.extend(add_p)
                else:
                    q.append(i)
                    while len(q):
                        item = q.pop()
                        result.append(item)
                        l = len(str(item))
                        if l >= k:
                            continue
                        if l < k - 1:
                            add_p = [int(str(item)+str(p)) for p in xrange(9,-1,-1)]
                            q.extend(add_p)
                        if (l == k - 1) and (item == int(str(n)[:l])):
                            add_p = [int(str(item)+str(p)) for p in xrange(int(str(n)[l]),-1,-1)]
                            q.extend(add_p)
                        if (l == k - 1) and (item < int(str(n)[:l])):
                            add_p = [int(str(item)+str(p)) for p in xrange(9,-1,-1)]
                            q.extend(add_p)
            return result
    

  • 0
    D

    The actual solution is much shorter than yours and does not involve any to_string operations.
    Print first 1337 numbers and see the obvious recursive pattern - as always with this kind of problems.


  • 0

    @xcc

    I used recursion to solve this problem in Java. Much shorter than your code. Just a small hint. :)


  • 0
    D

    @Nakanu Did your java code pass the timer test?
    I tried doing with buckets, I tried brute force with java's Collections and sorting by making a string to find lexi orders. Still haven't passed it! Any clues?


  • 0
    X

    Thanks, all.

    I have found a smart way. No recursion. But It's quite tricky.

    class Solution(object):
        def lexicalOrder(self, n):
            """
            :type n: int
            :rtype: List[int]
            """
            # return map(int, sorted(map(str, range(1,n + 1))))
            # ls = range(1, n + 1)
            # ls.sort(key=str)
            # return ls
            result = []
            k = len(str(n))
            start = int(str(n)[0])
            for i in xrange(10**(k-1), 10**k):
                if i%10 == 0:
                    tmp = i
                    nums = []
                    while not (tmp%10):
                        tmp /= 10
                        if tmp <= n:
                            nums.append(tmp)
                    result.extend(nums[::-1])
                if i <= n:
                    result.append(i)
    
            return result
    

  • 0

    @dixitk13164
    Hi, dixitk.
    Yea. My solution is accepted. Do u have a TLE problem? I thought about things like bucket or radix sort before. Then I found the recursion way to generate it directly without any sorting. I think the usage of Collections should be fine. But if you do it in string, definitely, it will cost lots of time on converting values into string and back to integer. String should be the main cause of your problem.

    My code:

    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>();
        for(int i = 1;i<=9;i++){
            if(i<=n){
                ans.add(i);
                helper(i,ans,n);
            }
            else{
                break;
            }
        }
        return ans;
    }
    private void helper(int last, List<Integer> ans, int n){
        int curr = 10*last;
        for(int i = 0;i<=9;i++){
            if(curr+i<=n){
                ans.add(curr+i);
                helper(curr+i,ans,n);
            }
            else{
                break;
            }
        }
    }

Log in to reply
 

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