TLE Kidding Me. Obviously fast.


  • 0
    B

    This causes a TLE in case of (9,8)
    After comparing with other accepted kernals in other questions, I ran all for 999 times and found it obviously faster in this case and return right result.
    The logic is recursion: first arrange [1,2,3,.... k] when k=n
    then the result of combine(n) will cover all result of combine(n-1) and those which replace one digit in all single list in result of combine(n-1).
    Not fast in most case but at least in this case (9,8) and works.
    Why TLE?

    public class Solution {
    
    public List<List<Integer>> combine(int n, int k) {
        if(k>n)
            return Collections.<List<Integer>>emptyList();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
        if(n==k){
            ArrayList<Integer> newlist = new ArrayList<Integer> ();
            for(int i = 1; i<= n; i++){
                newlist.add(i);
            }
            ans.add(newlist);
        }else{
            List<List<Integer>> pre = combine(n-1,k);
            for(final List<Integer> oldlist: pre){
                ans.add(oldlist);
                for(int j = 0; j<k;j++){
                    List<Integer> newlist = new ArrayList<Integer> (oldlist);
                    newlist.set(j,n);
                    ans.add(newlist);
                }
            }
        }
        return ans;
    
    }

  • 0
    J

    I don't know Java. But do you think copy the old list every time is efficient?


  • 0
    W

    I tried the same code but I don't the efficiency of copying old list is low since we eventually construct the same amount of lists. So I guess something wrong with the copying -- elements in lists point to the same Object and cause the evaluation of OJ into infinite loop.


  • 3
    N

    First of all, when it reported TLE with last input was (9, 8), it does not necessarily mean it is this input is error-prone, but means you got timed out when running this input. And in this case, input (9, 8), perfectly works. The problem is when input n - k > 1, for example, input (3, 1), your program will return [[1],[2],[3],[3]] which contains duplicates. Number of duplicates will get much more when the difference between n and k grows. That's where it cost more time. So unfortunately the algorithm has something fundamentally wrong : ( But, really genius thought!


  • 0
    B

    Thanks so much! You've pointed out the most valuable point.
    After consideration, I know it's wrong about my algorithm and it's also low efficient for general case. When I tried to get input(5,2) and the input(4,2) return something like {4,3;4,2;4,1;} by replacing the second position with '5', we get three same list. I have to remove duplicate and it's quite costly.


Log in to reply
 

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