Super Ugly Number (K Primes)

▶

Steps

setup

Initialize heap with first multiples of primes

We start by pushing the first multiples of each prime (2,7,13,19) into the min-heap. The ugly list starts with 1.

💡 This sets up the initial candidates for the super ugly numbers beyond 1.

Line:

for i, p in enumerate(primes):
    heapq.heappush(heap, (p, i, 0))

💡 The heap now contains the smallest multiples of each prime to begin merging.

extract_min

Extract smallest candidate 2

Pop the smallest element 2 from the heap, which is the next super ugly number candidate.

💡 Extracting the smallest candidate lets us add it to the ugly list if not a duplicate.

Line:

val, i, idx = heapq.heappop(heap)

💡 The smallest candidate is 2, so it will be added to the sequence.

insert

Add 2 to ugly list and push next multiple 4

Since 2 is not a duplicate, add it to ugly. Then push the next multiple of prime 2: 2 * ugly[1] = 4.

💡 Generating the next candidate from the same prime keeps the sequence growing correctly.

Line:

if val != ugly[-1]:
    ugly.append(val)
heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))

💡 The heap now includes 4, the next candidate from prime 2.

extract_min

Extract smallest candidate 4

Pop 4 from the heap, the next smallest candidate to consider.

💡 Extracting the smallest candidate lets us add it if unique.

Line:

val, i, idx = heapq.heappop(heap)

💡 4 is the next super ugly number candidate.

insert

Add 4 to ugly list and push next multiple 8

Add 4 to ugly since it's unique. Push next multiple from prime 2: 2 * ugly[2] = 8.

💡 Continuing to generate multiples from prime 2 extends the sequence.

Line:

if val != ugly[-1]:
    ugly.append(val)
heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))

💡 Heap now includes 8, the next candidate from prime 2.

extract_min

Extract smallest candidate 7

Pop 7 from the heap, the next smallest candidate.

💡 Extracting 7 to add to ugly if unique.

Line:

val, i, idx = heapq.heappop(heap)

💡 7 is the next super ugly number candidate.

insert

Add 7 to ugly list and push next multiple 49

Add 7 to ugly since unique. Push next multiple from prime 7: 7 * ugly[1] = 49.

💡 Generating multiples from prime 7 starts at ugly index 1.

Line:

if val != ugly[-1]:
    ugly.append(val)
heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))

💡 Heap now includes 49, the next candidate from prime 7.

extract_min

Extract smallest candidate 8

Pop 8 from the heap, the next smallest candidate.

💡 Extracting 8 to add to ugly if unique.

Line:

val, i, idx = heapq.heappop(heap)

💡 8 is the next super ugly number candidate.

insert

Add 8 to ugly list and push next multiple 14

Add 8 to ugly since unique. Push next multiple from prime 2: 2 * ugly[3] = 14.

💡 Continue generating multiples from prime 2.

Line:

if val != ugly[-1]:
    ugly.append(val)
heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))

💡 Heap now includes 14, the next candidate from prime 2.

extract_min

Extract smallest candidate 13

Pop 13 from the heap, the next smallest candidate.

💡 Extracting 13 to add to ugly if unique.

Line:

val, i, idx = heapq.heappop(heap)

💡 13 is the next super ugly number candidate.

insert

Add 13 to ugly list and push next multiple 26

Add 13 to ugly since unique. Push next multiple from prime 13: 13 * ugly[1] = 26.

💡 Generating multiples from prime 13 starts at ugly index 1.

Line:

if val != ugly[-1]:
    ugly.append(val)
heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))

💡 Heap now includes 26, the next candidate from prime 13.

extract_min

Extract smallest candidate 14

Pop 14 from the heap, the next smallest candidate.

💡 Extracting 14 to add to ugly if unique.

Line:

val, i, idx = heapq.heappop(heap)

💡 14 is the next super ugly number candidate.

insert

Add 14 to ugly list and push next multiple 28

Add 14 to ugly since unique. Push next multiple from prime 2: 2 * ugly[4] = 28.

💡 Continuing multiples from prime 2.

Line:

if val != ugly[-1]:
    ugly.append(val)
heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))

💡 Heap now includes 28, the next candidate from prime 2.

extract_min

Extract smallest candidate 19

Pop 19 from the heap, the next smallest candidate.

💡 Extracting 19 to add to ugly if unique.

Line:

val, i, idx = heapq.heappop(heap)

💡 19 is the next super ugly number candidate.

insert

Add 19 to ugly list and push next multiple 38

Add 19 to ugly since unique. Push next multiple from prime 19: 19 * ugly[1] = 38.

💡 Generating multiples from prime 19 starts at ugly index 1.

Line:

if val != ugly[-1]:
    ugly.append(val)
heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))

💡 Heap now includes 38, the next candidate from prime 19.

extract_min

Extract smallest candidate 26

Pop 26 from the heap, the next smallest candidate.

💡 Extracting 26 to add to ugly if unique.

Line:

val, i, idx = heapq.heappop(heap)

💡 26 is the next super ugly number candidate.

insert

Add 26 to ugly list and push next multiple 52

Add 26 to ugly since unique. Push next multiple from prime 13: 13 * ugly[2] = 52.

💡 Continuing multiples from prime 13.

Line:

if val != ugly[-1]:
    ugly.append(val)
heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))

💡 Heap now includes 52, the next candidate from prime 13.

extract_min

Extract smallest candidate 28

Pop 28 from the heap, the next smallest candidate.

💡 Extracting 28 to add to ugly if unique.

Line:

val, i, idx = heapq.heappop(heap)

💡 28 is the next super ugly number candidate.

insert

Add 28 to ugly list and push next multiple 32

Add 28 to ugly since unique. Push next multiple from prime 2: 2 * ugly[5] = 32.

💡 Continuing multiples from prime 2.

Line:

if val != ugly[-1]:
    ugly.append(val)
heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))

💡 Heap now includes 32, the next candidate from prime 2.

extract_min

Extract smallest candidate 32 (12th super ugly number)

Pop 32 from the heap, the 12th super ugly number in the sequence.

💡 Extracting the final answer from the heap.

Line:

val, i, idx = heapq.heappop(heap)
if val != ugly[-1]:
    ugly.append(val)

💡 32 is the 12th super ugly number.

import heapq

def nthSuperUglyNumber(n, primes):
    ugly = [1]  # STEP 1: Initialize ugly list
    k = len(primes)
    heap = []
    # STEP 1: Push first multiples of primes
    for i, p in enumerate(primes):
        heapq.heappush(heap, (p, i, 0))  # STEP 1
    while len(ugly) < n:
        val, i, idx = heapq.heappop(heap)  # STEP 2,4: Extract min
        if val != ugly[-1]:
            ugly.append(val)  # STEP 3: Add unique
        heapq.heappush(heap, (primes[i] * ugly[idx + 1], i, idx + 1))  # STEP 4: Push next multiple
    return ugly[-1]

if __name__ == '__main__':
    print(nthSuperUglyNumber(12, [2,7,13,19]))  # Output: 32

📊

Super Ugly Number (K Primes) - Watch the Algorithm Execute, Step by Step

Watching the heap operations and how new candidates are generated reveals the core of the k-way merge approach, which is hard to grasp from code alone.

insertmin-heap

2

0

7

1

13

2

19

3

extract_minmin-heap

7

0

19

1

13

2

Added: 2

insertmin-heap

4

0

7

1

13

2

19

3

extract_minmin-heap

7

0

19

1

13

2

Added: 4

insertmin-heap

7

0

8

1

13

2

19

3

extract_minmin-heap

8

0

19

1

13

2

Added: 7

insertmin-heap

8

0

19

1

13

2

49

3

extract_minmin-heap

13

0

19

1

49

2

Added: 8

insertmin-heapswap [1↔3]

13

0

14

1

49

2

19

3

extract_minmin-heap

14

0

19

1

49

2

Added: 13

insertmin-heapswap [2↔3]

14

0

19

1

49

2

26

3

extract_minmin-heapswap [1↔2]

19

0

49

1

26

2

Added: 14

insertmin-heapswap [2↔3]

19

0

26

1

49

2

28

3

extract_minmin-heap

26

0

28

1

49

2

Added: 19

insertmin-heapswap [2↔3]

26

0

28

1

49

2

38

3

extract_minmin-heapswap [1↔2]

28

0

49

1

38

2

Added: 26

insertmin-heap

28

0

38

1

49

2

52

3

extract_minmin-heapswap [1↔2]

38

0

52

1

49

2

Added: 28

insertmin-heapswap [0↔3]

32

0

38

1

52

2

49

3

extract_minmin-heap

38

0

49

1

52

2

Added: 32

Key Takeaways

✓ The min-heap efficiently merges multiple sorted sequences of multiples from each prime.

This insight is hard to see from code alone because the heap operations and candidate generation are intertwined.

✓ Duplicates are avoided by checking the last added ugly number before appending a new candidate.

Visualizing this check clarifies why duplicates do not appear in the final sequence.

✓ Each prime generates candidates by multiplying with progressively larger ugly numbers, ensuring all super ugly numbers are covered.

Watching the heap grow and shrink with these candidates shows the k-way merge in action.

Practice

1. You are given K sorted arrays and need to find the median of all elements combined without fully merging them. Which algorithmic approach guarantees an optimal solution in terms of time complexity for large inputs?

easy

A. Merge all arrays fully into one sorted array and then pick the median.

B. Use binary search on the value range combined with counting elements ≤ mid across arrays.

C. Apply a greedy approach by repeatedly picking the smallest current element from arrays until median is found.

D. Use dynamic programming to build a table of medians for subarrays and combine results.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the median without merging all arrays fully, which is costly for large inputs.

2. Step 2: Identify optimal approach

   Binary search on the value range combined with counting elements ≤ mid leverages sorted arrays and avoids full merge, achieving better time complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search on value range is known optimal for this problem [OK]

Hint: Binary search on value range beats full merge [OK]

Common Mistakes:

• Assuming full merge is always optimal
• Confusing greedy with binary search
• Misapplying DP to median finding

2. You have an array where each element is at most k positions away from its sorted position. Which algorithmic approach guarantees the most efficient sorting in terms of time complexity?

easy

A. Use a standard full sort like quicksort or mergesort on the entire array.

B. Use a min-heap of size k+1 to iteratively extract the smallest element and build the sorted array.

C. Apply a greedy approach by swapping elements only when they are out of order by more than k positions.

D. Use dynamic programming to find the minimum number of swaps needed to sort the array.

Solution

1. Step 1: Understand the problem constraints

   The array is almost sorted, with each element at most k positions away from its correct position.

2. Step 2: Identify the optimal approach

   A min-heap of size k+1 efficiently keeps track of the next smallest element within the window of possible positions, allowing sorting in O(n log k) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Min-heap size k+1 matches the maximum displacement constraint [OK]

Hint: Min-heap size k+1 exploits limited disorder [OK]

Common Mistakes:

• Assuming full sort is always best
• Trying greedy swaps without heap
• Using DP which is unnecessary here

3. The following code attempts to merge k sorted arrays using divide and conquer. Which line contains a subtle bug that causes incorrect output when the number of arrays is odd?

medium

A. Line 5: for i in range(0, len(arrays), 2):

B. Line 8: merged_arrays.append(merge_two_arrays(arr1, arr2))

C. Line 7: arr2 = arrays[i+1]

D. Line 10: return arrays[0]

Solution

1. Step 1: Identify handling of odd number of arrays

   When number of arrays is odd, accessing arrays[i+1] without check causes IndexError or misses last array.

2. Step 2: Correct fix

   Use conditional: arr2 = arrays[i+1] if i+1 < len(arrays) else [] to handle last array properly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Line 7 lacks boundary check -> bug on odd arrays [OK]

Hint: Check array bounds when accessing pairs in loop [OK]

Common Mistakes:

• Forgetting boundary check for last array
• Merging empty array incorrectly
• Returning wrong array index

4. Consider the following buggy code for finding the nth ugly number. Which line contains the subtle bug that causes incorrect results or performance issues?

medium

A. Line 3: heap initialization with [1]

B. Line 4: Missing initialization of the 'seen' set

C. Line 7: Loop runs n times popping from heap

D. Line 10: Multiplying ugly by factors 2, 3, and 5

Solution

1. Step 1: Identify missing duplicate check

   The 'seen' set is not initialized and the check to avoid pushing duplicates is missing, causing duplicates to be pushed repeatedly.

2. Step 2: Understand impact of missing 'seen'

   Without 'seen', the heap grows unnecessarily large with duplicates, causing performance degradation and possibly incorrect nth number due to repeated values.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing 'seen' set causes duplicates and performance issues [OK]

Hint: Always track seen elements to avoid duplicates in heap [OK]

Common Mistakes:

• Forgetting to initialize or use 'seen'
• Assuming heap automatically avoids duplicates

5. Suppose you want to merge k sorted lists but now each list can contain duplicate values that must be preserved, and you want to return the top M smallest elements overall efficiently. Which modification to the standard divide and conquer approach is best?

hard

A. Continue using divide and conquer merging all lists fully, then slice the first M elements from the merged list.

B. Use dynamic programming to memoize merged prefixes and retrieve top M elements.

C. Concatenate all lists, sort them fully, then return first M elements.

D. Use a min heap to always extract the smallest current node among all lists until M elements are collected.

Solution

1. Step 1: Understand the requirement for top M elements

   We only need the first M smallest elements, not the full merged list.

2. Step 2: Analyze approaches for efficiency

   Divide and conquer merges all lists fully (O(N log k)), which is wasteful if M << N. Concatenation and sort is O(N log N). Min heap approach extracts smallest nodes one by one, stopping after M elements, achieving O(M log k).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min heap approach efficiently returns top M elements without full merge [OK]

Hint: Min heap extracts smallest nodes incrementally, ideal for top M [OK]

Common Mistakes:

• Merging all lists fully then slicing wastes time
• Sorting all nodes is inefficient for partial results
• Dynamic programming is not applicable here