Why is this recursion method TLE? (for Lexicographical Numbers)


  • 0

    I don't really understand why my recursive solution got TLE, I tested locally, it finished with these two test cases: 10458 and 14959 in 26 and 34 ms respectively, however, got TLE on OJ, any help where I could cut the runtime would be greatly appreciated.

    
        public List<Integer> lexicalOrder(int n) {
            List<Integer> result = new ArrayList();
            int insertPosition = 0;
            return addNumbers(result, 1, insertPosition, n);
        }
        
        private List<Integer> addNumbers(List<Integer> result, int insertNumber, int insertPosition, int n) {
            int i;
            for(i = 0; i < 9; i++){
                if(insertNumber+i > n) return result;
                result.add(insertPosition+i, insertNumber+i);
                if((insertNumber+i) % 10 == 0 && (insertNumber+i) == (insertNumber+10)) break;
            }
            while((insertNumber+i) % 10 != 0 && (insertNumber+i) <= n){
                result.add(insertPosition+i, insertNumber+i);
                i++;
            }
            //find next insert position:
            insertPosition = result.indexOf((insertNumber+i)/10);
            return addNumbers(result, insertNumber+i, insertPosition+1, n);
        }
    
    

  • 0
    H

    try this case:5000000,maybe you will get TLE


  • 0
    This post is deleted!

Log in to reply
 

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