Please help me with my TLE issue with O(nk) Java solution


  • 0
    H

    The idea is based on [Ugly Number II][1]. I use an ArrayList to store 'k' queues.
    And for each loop, I find the minimum from all top values, remove it/them. then add new number into each queue. the minimum number I find in last loop will be the return value. Please see my code below

    public int nthSuperUglyNumber(int n, int[] primes) {
        if(primes==null||primes.length==0||n<=0)
            return -1;
        
        if(n==1)
            return 1;
        
        int rv = 1;
        ArrayList<Queue<Integer>> qs = new ArrayList<Queue<Integer>>();
        for(int x:primes){  //O(k)
            Queue<Integer> q = new LinkedList<Integer>();
            q.add(x);
            qs.add(q);
        }
        
        while(n>1){ //O(n)
            int min = Integer.MAX_VALUE;
            for(int i=0;i<primes.length;i++){   //O(k)
                min=Math.min(min,qs.get(i).peek());
            }
            rv=min;
            for(int i=0;i<primes.length;i++){   //O(k)
                Queue<Integer> q = qs.get(i);
                if(q.peek()==min)
                    q.remove();
                q.add(min*primes[i]);
            }
            n--;
        }
        
        return rv;
    }
    

    I think time complexity should be O(nk)

    • Create/Initial ArrayList = O(k)
    • Loop n times = O(n*2k) = O(nk)
      • find minimum: O(k)
      • remove minimum and add new number into queue: O(k)

    But OJ returns me a TLE error when I run my code against this test case,

    100000 [7,19,29,37,41,47,53,59,61,79,83,89,101,103,109,127,131,137,139,157,167,179,181,199,211,229,233,239,241,251]
    

    I try to find out the most time consuming part, so I ran my code in eclipse and printed out time cost for creating ArrayList, and time cost for every 1000 loops. Please see below,

     create list:1 100000:0 99000:12 98000:6 97000:1 96000:1 95000:1 94000:1 93000:0 92000:1 91000:1 90000:1 89000:1 88000:0 87000:1 86000:1 85000:0 84000:0 83000:1 82000:1 81000:1 80000:1 79000:1 78000:1 77000:1 76000:1 75000:1 74000:1 73000:0 72000:70 71000:1 70000:1 69000:0 68000:0 67000:1 66000:1 65000:1 64000:1 63000:0 62000:1 61000:0 60000:1 59000:1 58000:0 57000:1 56000:0 55000:1 54000:0 53000:1 52000:1 51000:0 50000:1 49000:1 48000:1 47000:0 46000:1 45000:851 44000:1 43000:1 42000:0 41000:1 40000:0 39000:1 38000:1 37000:0 36000:1 35000:0 34000:0 33000:1 32000:0 31000:1 30000:1 29000:0 28000:1 27000:0 26000:1 25000:1 24000:0 23000:1 22000:0 21000:0 20000:1 19000:0 18000:1 17000:1 16000:0 15000:1 14000:0 13000:1 12000:1 11000:1 10000:1 9000:0 8000:1 7000:1 6000:1 5000:1 4000:1 3000:1 2000:0 1000:0 total:1011
    

    the return value is 1092889481, and the total time cost is 1011ms. From the result we can find the most time consuming part is when 'n' between 44000 and 45000, which costed 851ms(I ran my code twice, the costs are slightly different, but both of them showing 44000-45000 is the most expensive part).

    Then I printed out time cost for each loop when 'n' between 44000 and 45000, but I found the time cost was rounded to 0 for each one(because the result is too long to post, so I'll just describe it here. And I also ran my code twice). Based on it, seems nothing really expensive.

    I was confused by the TLE and also by my testing. Could anyone please help me with it?

    Why the two tests showing different result, one said this part is expensive, one said it's not? What is wrong? What is missing? Why my code got TLE?

    Any help/comment would be appreciated. Thank you.
    [1]: https://leetcode.com/problems/ugly-number-ii/


Log in to reply
 

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