Java three methods, 23ms, 36 ms, 58ms(with heap), performance explained


  • 111
    C

    Basic idea is same as ugly number II, new ugly number is generated by multiplying a prime with previous generated ugly number. One catch is need to remove duplicate

    Let's start with the common solution from ugly number II 36 ms, Theoretically O(kN)

    public int nthSuperUglyNumberI(int n, int[] primes) {
        int[] ugly = new int[n];
        int[] idx = new int[primes.length];
    
        ugly[0] = 1;
        for (int i = 1; i < n; i++) {
            //find next
            ugly[i] = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j++)
                ugly[i] = Math.min(ugly[i], primes[j] * ugly[idx[j]]);
            
            //slip duplicate
            for (int j = 0; j < primes.length; j++) {
                while (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;
            }
        }
    
        return ugly[n - 1];
    }
    

    If you look at the above solution, it has redundant multiplication can be avoided, and also two for loops can be consolidated into one. This trade-off space for speed. 23 ms, Theoretically O(kN)

    public int nthSuperUglyNumber(int n, int[] primes) {
            int[] ugly = new int[n];
            int[] idx = new int[primes.length];
            int[] val = new int[primes.length];
            Arrays.fill(val, 1);
    
            int next = 1;
            for (int i = 0; i < n; i++) {
                ugly[i] = next;
                
                next = Integer.MAX_VALUE;
                for (int j = 0; j < primes.length; j++) {
                    //skip duplicate and avoid extra multiplication
                    if (val[j] == ugly[i]) val[j] = ugly[idx[j]++] * primes[j];
                    //find next ugly number
                    next = Math.min(next, val[j]);
                }
            }
    
            return ugly[n - 1];
        }
    

    Can we do better? Theoretically yes, by keep the one candidates for each prime in a heap, it can improve the theoretical bound to O( log(k)N ), but in reality it's 58 ms. I think it's the result of using higher level object instead of primitive. Can be improved by writing an index heap (http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html)

    public int nthSuperUglyNumberHeap(int n, int[] primes) {
        int[] ugly = new int[n];
    
        PriorityQueue<Num> pq = new PriorityQueue<>();
        for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
        ugly[0] = 1;
    
        for (int i = 1; i < n; i++) {
            ugly[i] = pq.peek().val;
            while (pq.peek().val == ugly[i]) {
                Num nxt = pq.poll();
                pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
            }
        }
    
        return ugly[n - 1];
    }
    
    private class Num implements Comparable<Num> {
        int val;
        int idx;
        int p;
    
        public Num(int val, int idx, int p) {
            this.val = val;
            this.idx = idx;
            this.p = p;
        }
    
        @Override
        public int compareTo(Num that) {
            return this.val - that.val;
        }
    }

  • 0
    C

    What does the p mean in the last solution?


  • 0
    C

    p means value of the primes


  • 25
    I

    Actually you don't need an extra array in version 2 (de-duplication). This would work:

    public int nthSuperUglyNumber(int n, int[] primes) {
        int [] res = new int[n];
        res[0] = 1;
        int [] cur = new int[primes.length];
        
        for(int i = 1; i < n; i++){
            res[i] = Integer.MAX_VALUE;
            for(int j = 0; j < primes.length; j++){
                if (primes[j] * res[cur[j]] == res[i-1]) {
                    cur[j]++;
                }
                res[i] = Math.min(res[i], primes[j]*res[cur[j]]);
            }
        }
        return res[n-1];
    }

  • 0
    C

    It's a trade off between space and speed, with extra array the multiplication inside if can be omitted


  • 0
    I

    I see. makes sense.


  • 0
    L

    The O(nlogk) solution is better than the trivial O(nk) solution. Either by embedding the index info in a heap node (like the Num class in this solution) or maintaining an external mapping would work.


  • 0
    C

    agree with you, there's a data structure for that, it's called indexed heap


  • 1
    F

    The first solution :
    //slip duplicate
    while (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;
    equals:
    if (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;


  • 4
    F

    I came up with the solution with a heap at first, but then I gave it up because I thought the time complexity was O(nklogk). This is due to the inner loop at most pops out all the elements in the heap, which have a number of k. So, the time complexity of the inner loop is: logk + log(k-1) + log(k-2) +...+log1=O(klogk). As the inner loop runs n times, so the overall time complexity is O(nklogk). Anyone could tell me where I am wrong?


  • 1
    S

    how to prove the time complexity of last solution with a while loop inside the for loop?


  • 2
    H

    In the first solution, why do you use a while loop like here?

    for (int j = 0; j < primes.length; j++) {
        while (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;
    }
    

    shouldnt it be an if statement? wouldnt the while loop never be traversed more than once?


  • 1
    E

    Agree with you, I thought it should be O(nklogk), too. I could be wrong, but the author did not explain the reason behind O(nlogk) theory.


  • 0
    C

    @hide you can replace with if statement, same result as while. I used while just to make the meaning clear to myself.


  • 0
    G

    Great solution, thank you for sharing!!!


  • 8
    H

    @crackAlgo personally, I think this would make the intention more clear, using if instead of while, and using == instead of <=:

    for (int j = 0; j < primes.length; j++) {
        if(primes[j] * ugly[idx[j]] == ugly[i]) idx[j]++;
    }

  • 0

    @isax Can you explain more on

    if (primes[j] * res[cur[j]] == res[i-1]) {
        cur[j]++;
    }
    

    And the intuition on int[] cur, thanks.


  • 0
    H

    @Roderickgao cur[j] is the current index that the prime[j] builds from in res[]. He increases the current index that the prime number builds from, if its equal to the last ugly number. The problem is that while it does avoid double for loops, it still requires redundant multiplication. It's a trade-off you could discuss.

    Just tested both. OP's optimization is 22ms. isax's is 31ms.


  • 7

    For the heap solution, instead of using the Num class, I use a 1x3 array to store the values and to avoid creating new objects when adding to the priority queue, I modify the values of the polled objects. But the performance is similar. Following is my code:

    public class Solution {
        public int nthSuperUglyNumber(int n, int[] primes) {
            
            PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
                @Override
                public int compare(int[] n1, int[] n2){
                    return n1[0] - n2[0];
                }
                //n[0] current value, n[1] current index, n[2] base value
            });
            
            int[] ans = new int[n];
            ans[0] = 1;
            
            for(int i = 0; i < primes.length; i++){
                pq.offer(new int[] {primes[i], 0, primes[i]});
            }
            
            for(int i = 1; i < n; i++){
                int next = pq.peek()[0];
                ans[i] = next;
                while(pq.peek()[0] == next){
                    int[] cur = pq.poll();
                    cur[0] = cur[2]*ans[cur[1]];
                    cur[1] = cur[1]+1;
                    pq.offer(cur);
                }
            }
            
            return ans[n-1];
        }
    }
    

    I think the overhead of this solution is that we have to put all primes to the heap first, this takes Klog(K), which makes the solution slower (assume there are K primes).

    Besides, the remain part takes complexity between Nlog(K) and NKlog(K), i.e for the best case there is only one peek == next, it takes log(K), and for the worst case, all objects in the heap == next, so it takes Klog(K). So this loop is not necessarily < KN.

    That's why the heap solution is slower than the KN solution.


  • 0

    @hide Thanks.


Log in to reply
 

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