Heap & Priority Queue: Smallest Range Covering Elements from K Lists & Construct Target Array With Multiple Sums

This chapter concludes the Heap / Priority Queue Data Structures & Algorithms series by exploring two advanced, hard-level problems on LeetCode. These problems test our ability to design optimal greedy search strategies, maintain dynamic window boundaries using heaps, and apply reverse engineering techniques to avoid exponential time complexities.

1. Problem 1: Smallest Range Covering Elements from K Lists

Core Problem Statement

Given $K$ sorted lists of integers, we need to find the smallest range $[a, b]$ such that at least one element from every single list is included within that range. If multiple ranges have the same minimum length, we choose the one with the smaller starting value.

Real-Life Analogy: The Event Coordination Committee

Imagine you have $K$ different committees (lists), and each committee has a sorted list of preferred meeting times. You want to find the shortest continuous time window (range) so that at least one member from every single committee is available to attend. Since all individual lists are already sorted internally, you always want to test the earliest available times across committees, systematically sliding your time window forward by removing the earliest (minimum) arrival time and bringing in the next available time from that same committee.

2. Naive Approach vs. Optimal Min-Heap Strategy

The Brute Force Trap

If we attempt a naive brute force approach:

1. Flatten all lists or generate every possible combination of ranges from the $K$ lists.
2. For each generated range, check if it contains at least one element from each of the $K$ lists.
3. This requires evaluating roughly $O(N \cdot K)$ total elements, leading to an intractable time complexity of $O((N \cdot K)^3)$, which will immediately result in Time Limit Exceeded (TLE) in production or competitive programming environments.

The Optimal Min-Heap Strategy

Instead of testing every combination, we can maintain a Min-Heap containing exactly one element from each of the $K$ lists at any given time:

• The top of the Min-Heap always gives us the current minimum element across all active representations.
• We track the maximum element currently present in our active window.
• The difference between the maximum and minimum gives our current range width.
• To shrink or optimize the range, we extract the minimum element from the heap, calculate the new range width if it beats our historical minimum, and push the next consecutive element from the exact same source list into the heap.

3. Step-by-Step Evolution of the Sliding Range

Let's trace how the active range evolves using the Min-Heap approach:

4. Complete Code Implementation (C++)

Here is the clean, production-grade implementation for solving the Smallest Range problem using a Min-Heap and custom pair tracking:

#include <vector>
#include <queue>
#include <climits>

using namespace std;

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        // Min-heap storing: {element_value, {row_index, col_index}}
        priority_queue<
            pair<int, pair<int, int>>, 
            vector<pair<int, pair<int, int>>>, 
            greater<pair<int, pair<int, int>>>
        > minHeap;

        int maxi = INT_MIN;
        int k = nums.size();

        // Step 1: Insert the first element of each list into the Min-Heap
        for (int i = 0; i < k; ++i) {
            minHeap.push({nums[i][0], {i, 0}});
            maxi = max(maxi, nums[i][0]);
        }

        int startRange = minHeap.top().first;
        int endRange = maxi;
        int minRangeLength = endRange - startRange;

        // Step 2: Process elements while all K lists are represented in the heap
        while (minHeap.size() == k) {
            auto curr = minHeap.top();
            minHeap.pop();

            int val = curr.first;
            int row = curr.second.first;
            int col = curr.second.second;

            // Check and update the smallest range
            int currentRangeLength = maxi - val;
            if (currentRangeLength < minRangeLength) {
                minRangeLength = currentRangeLength;
                startRange = val;
                endRange = maxi;
            } else if (currentRangeLength == minRangeLength) {
                if (val < startRange) {
                    startRange = val;
                    endRange = maxi;
                }
            }

            // Step 3: If the same list has a next element, push it to the heap
            if (col + 1 < nums[row].size()) {
                int nextVal = nums[row][col + 1];
                minHeap.push({nextVal, {row, col + 1}});
                maxi = max(maxi, nextVal);
            } else {
                // If any list runs out of elements, we cannot cover all K lists anymore
                break;
            }
        }

        return {startRange, endRange};
    }
};

5. Problem 2: Construct Target Array With Multiple Sums

Core Problem Statement

You are given an array of integers target of size $N$. Starting with an array of all ones [1, 1, ..., 1] of the same size, can you construct the target array by repeatedly performing the following operation:

1. Choose any index $i$ and set its value equal to the sum of all elements in the current array.
2. Return true if you can form the target array, otherwise false.

Real-Life Analogy: Rewinding a Magic Sum Machine

Imagine baking a loaf of bread where every day you replace one ingredient's weight with the sum of all ingredients currently in the bowl. Working forward from [1, 1] to [8, 5] feels like guessing in the dark because multiple summation paths branch out. However, if we work backward from [8, 5] to [1, 1], the path is completely deterministic: the largest number in the current array must have been the one that was just created by summing everything else!

6. Forward Construction vs. Reverse Engineering

7. Handling Edge Cases & Avoiding TLE with Modulo Arithmetic

When working backward from a very large target value (e.g., [1, 1000000000]), repeatedly subtracting the remaining sum will cause Time Limit Exceeded (TLE).

The Modulo Optimization

Instead of step-by-step subtraction, we use the Modulo Operator (%) to fast-forward through identical subtraction sequences:

Note: Special care must be taken when the modulo operation yields 0 or when handling small arrays of size 1 (e.g., [1] vs [10]).

8. Complete Code Implementation (C++)

Here is the fully optimized, production-grade C++ solution for Construct Target Array With Multiple Sums using a Max-Heap and modulo arithmetic:

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    bool isPossible(vector<int>& target) {
        priority_queue<long long> maxHeap;
        long long sum = 0;

        for (int x : target) {
            maxHeap.push(x);
            sum += x;
        }

        while (maxHeap.top() != 1) {
            long long maxElement = maxHeap.top();
            maxHeap.pop();

            long long remainingSum = sum - maxElement;

            // Base validation checks
            if (remainingSum <= 0 || maxElement <= remainingSum) {
                return false;
            }

            long long prevElement = maxElement % remainingSum;
            sum = remainingSum + prevElement;

            // Handle edge case where modulo results in 0
            if (prevElement == 0) {
                if (remainingSum != 1) {
                    return false;
                }
                prevElement = 1;
            }

            maxHeap.push(prevElement);
        }

        return true;
    }
};

9. Summary and Key Takeaways

• Min-Heaps are indispensable when you need continuous access to the global minimum across multiple independent, sorted streams of data.
• Reverse Engineering transforms ambiguous, branching forward-simulation problems into deterministic, linear backward-reduction workflows.
• Modulo Arithmetic (%) acts as a crucial optimization tool to eliminate redundant subtraction loops and prevent Time Limit Exceeded (TLE) errors in numeric reduction problems.
• Always validate boundary conditions such as negative remaining sums, division/modulo by zero, and single-element array edge cases.