Advanced Heap Problems

These hard-level problems combine heaps with other techniques: BFS for 3D water trapping, sweep line for skylines, and greedy optimization for team performance. They appear frequently in FAANG interviews and require deep understanding of when and how to maintain heap invariants.

Problem 1: Super Ugly Number

import heapq

def nthSuperUglyNumber(n: int, primes: list[int]) -> int:
    """Find the nth super ugly number using a min-heap.

    Strategy:
    1. Start with 1 in the heap
    2. Pop the smallest ugly number
    3. Multiply it by each prime and push results
    4. Use a set to avoid duplicates
    5. The nth popped value is our answer

    Time: O(n * k * log(n * k)) where k = len(primes)
    Space: O(n * k)

    ML Application: Generating candidate hyperparameter values
    in grid search where parameters are multiples of base values.
    """
    heap = [1]
    seen = {1}
    ugly = 1

    for _ in range(n):
        ugly = heapq.heappop(heap)
        for prime in primes:
            next_ugly = ugly * prime
            if next_ugly not in seen:
                seen.add(next_ugly)
                heapq.heappush(heap, next_ugly)

    return ugly

# Optimized version using pointers (avoids duplicates naturally)
def nthSuperUglyNumberOptimized(n: int, primes: list[int]) -> int:
    """Optimized with pointer approach - O(n * k) time, O(n) space."""
    k = len(primes)
    ugly = [0] * n
    ugly[0] = 1
    indices = [0] * k  # pointer for each prime

    for i in range(1, n):
        # Next candidates: each prime * ugly[its pointer]
        candidates = [primes[j] * ugly[indices[j]] for j in range(k)]
        ugly[i] = min(candidates)

        # Advance pointers for all primes that produced this value
        for j in range(k):
            if candidates[j] == ugly[i]:
                indices[j] += 1

    return ugly[n - 1]

# Test
print(nthSuperUglyNumber(12, [2, 7, 13, 19]))  # 32
print(nthSuperUglyNumberOptimized(12, [2, 7, 13, 19]))  # 32

Problem 2: The Skyline Problem

import heapq

def getSkyline(buildings: list[list[int]]) -> list[list[int]]:
    """Compute the skyline using a sweep line with a max-heap.

    Strategy:
    1. Create events: (x, -height, right) for starts,
       (right, 0, 0) for ends
    2. Sort events by x-coordinate
    3. Use a max-heap to track active building heights
    4. When the max height changes, record a key point

    Time: O(n log n)
    Space: O(n)

    ML Application: Envelope detection in signal processing -
    finding the upper envelope of overlapping frequency bands
    in audio/speech features for ML models.
    """
    # Create events: start events have negative height for sorting
    events = []
    for left, right, height in buildings:
        events.append((left, -height, right))  # building start
        events.append((right, 0, 0))           # building end

    # Sort: by x, then by height (starts before ends at same x)
    events.sort()

    # Max-heap: (-height, right_edge)
    # Initialize with ground level
    result = []
    heap = [(0, float('inf'))]  # ground level never expires
    prev_max_height = 0

    for x, neg_h, right in events:
        if neg_h != 0:
            # Building start: add to heap
            heapq.heappush(heap, (neg_h, right))

        # Lazy deletion: remove buildings that have ended
        while heap[0][1] <= x:
            heapq.heappop(heap)

        current_max_height = -heap[0][0]

        if current_max_height != prev_max_height:
            result.append([x, current_max_height])
            prev_max_height = current_max_height

    return result

# Test
buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
print(getSkyline(buildings))
# [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

Problem 3: Trapping Rain Water II (3D)

import heapq

def trapRainWater(heightMap: list[list[int]]) -> int:
    """Trap rain water on a 2D elevation map (3D problem).

    Strategy: BFS from the boundary inward using a min-heap.
    1. Push all boundary cells into a min-heap
    2. Pop the lowest boundary cell
    3. Check its unvisited neighbors:
       - If neighbor is lower, it traps water (difference in height)
       - Push neighbor with max(its height, current boundary height)
    4. The heap always processes the lowest "wall" first

    Time: O(m * n * log(m * n))
    Space: O(m * n)

    ML Application: Terrain analysis in geospatial ML -
    computing watershed boundaries and water accumulation
    for flood prediction models.
    """
    if not heightMap or not heightMap[0]:
        return 0

    m, n = len(heightMap), len(heightMap[0])
    visited = [[False] * n for _ in range(m)]
    heap = []

    # Push all boundary cells
    for i in range(m):
        for j in range(n):
            if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                heapq.heappush(heap, (heightMap[i][j], i, j))
                visited[i][j] = True

    water = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while heap:
        height, x, y = heapq.heappop(heap)

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = True
                # Water trapped = max(0, boundary_height - cell_height)
                water += max(0, height - heightMap[nx][ny])
                # New boundary is the max of current boundary and cell
                new_height = max(height, heightMap[nx][ny])
                heapq.heappush(heap, (new_height, nx, ny))

    return water

# Test
heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
print(trapRainWater(heightMap))  # 4

heightMap2 = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
print(trapRainWater(heightMap2))  # 10

Problem 4: Maximum Performance of a Team

import heapq

def maxPerformance(n: int, speed: list[int], efficiency: list[int],
                   k: int) -> int:
    """Maximize team performance = sum(speed) * min(efficiency).

    Strategy:
    1. Sort engineers by efficiency in DESCENDING order
    2. Iterate: each engineer is the "minimum efficiency" candidate
    3. Maintain a min-heap of size k for the best speeds
    4. Performance = speed_sum * current_efficiency

    Why this works: By processing in descending efficiency order,
    when we consider engineer i, all previously seen engineers
    have efficiency >= efficiency[i]. So min(efficiency) = efficiency[i].

    Time: O(n log n + n log k)
    Space: O(n + k)

    ML Application: Team formation for ML projects - selecting
    engineers where "speed" = coding velocity and "efficiency" =
    code quality, optimizing for total productive output.
    """
    MOD = 10**9 + 7

    # Sort by efficiency descending
    engineers = sorted(zip(efficiency, speed), reverse=True)

    speed_heap = []  # min-heap of speeds in current team
    speed_sum = 0
    max_perf = 0

    for eff, spd in engineers:
        # Add this engineer
        heapq.heappush(speed_heap, spd)
        speed_sum += spd

        # If team is too large, remove the slowest
        if len(speed_heap) > k:
            speed_sum -= heapq.heappop(speed_heap)

        # Current performance: this engineer has the min efficiency
        max_perf = max(max_perf, speed_sum * eff)

    return max_perf % MOD

# Test
print(maxPerformance(6, [2,10,3,1,5,8], [5,4,3,9,7,2], 2))  # 60
print(maxPerformance(6, [2,10,3,1,5,8], [5,4,3,9,7,2], 3))  # 68