Why Time Comlexity is O(ans)? I thought inserting to minHeap is O(logN) and we do it multiple times
That’s what I’m wondering too. I feel like it should be log something.
I couldn’t come up with a heap solution so used 3 pointers. Although it uses more memory the time complexity is better I think? - O(1) lookup vs log(n) for heap
res = [1]
pointers = [[2, 0], [3, 0], [5, 0]]
while len(res) < n:
i = min(pointers, key = lambda x: x[0] * res[x[1]])
if res[i[1]] * i[0] != res[-1]:
res.append(res[i[1]] * i[0])
i[1] += 1
return res[-1]
interesting solution. I think it does the same thing as the heap solution except finding the running minimum is done using min instead. The time complexity would be slower cuz min is O(n).
I think the time complexity should be O(ans * logans)?
yup, I had the same thought and found this comment confirming O(n * log n), where n is the n-th ugly number
yep same.
1407 returns 536870912, so this will never be O(N). More like O(3 * n) * o(2 * log n). For the 2,3,5 iteration per n, and for both shifting down insertion and deletion of min heap value.
So O(N log N)
class Solution:
def nthUglyNumber(self, n: int) → int:
ugly = [1]
i2, i3, i5 = 0, 0, 0
while n > 1:
n2, n3, n5 = ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5
mi = min(n2, n3, n5)
if mi == n2:
i2 += 1
if mi == n3:
i3 += 1
if mi == n5:
i5 += 1
ugly.append(mi)
n -= 1
return ugly[-1]
Guys, since you take money for this course, could you please ensure that all information is correct? It is not the first mistake that I found:
“The “next element” is 3. Taking 3 and multiplying it by 2, 3, and 5, while checking that 6, 9, and 15 haven’t been generate yet, we insert them into our list. The new list, in sorted order, is now [1, 2, 3, 4, 5, 6, 9, 10].”
As you can see the list list doesn’t contain 15.
These small mistakes here and there make reading and learning a lot more difficult, tbh.
The time complexity of this solution is not wrong (in the sense that it’s linear), but I do find it a bit twisted to understand. Here’s my take on it:
At each iteration (except for the 1st iter), we remove one element and insert at most 3 elements so the size of the priority queue will grow by 2 at most at each iteration. The starting queue length is 3. At the n-1th iteration we will get the n-th ulgy number and there will be at most 3+2*(n-1)=2n+1 elements in the priority queue.
Min deletion and Insertion in a priority queue takes O(log(Size)).
So the time complexity is O(log(3)+log(5)+…log(2n+1)) = O(nlog(n)). For example, when n = 1407, ans = 536870912, time complexity is approximately O(1407*log(1407)), not O(536870912). Of course, magnitude-wise, it’s not wrong since they are both linear. Just thought O(nlog(n)) is more straightforward to understand.
I like the idea behind this alternative solution. At each iteration, the min is actually fixed at O(3) ~= O(1) so time complexity wise, I’d say it’s equivalent. Submitting via leetcode confirms the same (to reach roughly equivalent leetcode speed %, the original implementation needs to be optimized a bit. Reference: https://leetcode.com/problems/ugly-number-ii/discuss/69373/Short-and-O(n)-Python-and-C%2B%2B
def nthUglyNumber(self, n):
ugly = [1]
i2 = i3 = i5 = 0
while len(ugly) < n:
while ugly[i2] * 2 <= ugly[-1]: i2 += 1
while ugly[i3] * 3 <= ugly[-1]: i3 += 1
while ugly[i5] * 5 <= ugly[-1]: i5 += 1
ugly.append(min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5))
return ugly[-1]
Totally agree on this one