# AC PriorityQueue Solution

• ``````public int nthUglyNumber(int n) {
if(n<=0)    return 0;
PriorityQueue<Long> queue = new PriorityQueue<>();
Set<Long> set = new HashSet<>();
queue.offer((long)1);
long num=0;
while(n>0 && !queue.isEmpty()){
num = queue.poll();
if(set.contains(num))   continue;           //remove duplicate
queue.offer(num*2);
queue.offer(num*3);
queue.offer(num*5);
n--;
}
return (int)num;
}
``````

• I think this is a great solution and can save a lot of space when the N is very very large. All the other dynamic programming solutions wont be as effective when N is very large as space will be a constrain.

• @ddoshi5
The space complexity of the DP solution is O(n).

For this solution, to generate nth number, there will be n numbers in the set, which means the time complexity is also O(n), plus the space for ProrityQueue, which will also be O(n). Therefore, this solution actually uses more space than DP solution.......

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