Merge K Sorted Arrays

🎯

Merge K Sorted Arrays

mediumHEAPAmazonGoogleMicrosoft

Imagine you have multiple sorted logs from different servers and you want to combine them into one sorted log to analyze the overall system behavior.

💡 This problem involves merging multiple sorted arrays into one sorted array. Beginners often struggle because merging two arrays is straightforward, but merging k arrays efficiently requires a different approach than just repeatedly merging pairs.

📋

Problem Statement

Given k sorted arrays, merge them into one sorted array. Input: A list of k arrays, each sorted in ascending order. Output: A single sorted array containing all elements from the k arrays.

1 ≤ k ≤ 10^40 ≤ length of each array ≤ 10^4Total number of elements across all arrays ≤ 10^5-10^9 ≤ element values ≤ 10^9

💡

Example

Input"[[1,4,5],[1,3,4],[2,6]]"

Output[1,1,2,3,4,4,5,6]

We merge the three sorted arrays into one sorted array by picking the smallest elements step-by-step.

• k = 1 with one empty array → output is []
• All arrays empty → output is []
• Arrays with duplicate elements → duplicates appear in output
• Arrays of varying lengths including some empty → output merges all correctly

⚠️

Common Mistakes

Not handling empty arrays

Code crashes or returns incorrect results

✅ Check if array is empty before accessing elements

Using sort on combined array without considering input size

Solution is too slow and times out on large inputs

✅ Use min heap or divide and conquer to optimize

Incorrectly updating indices when pushing next elements to heap

Infinite loops or missing elements in output

✅ Carefully track array and element indices when pushing to heap

Not merging last array when number of arrays is odd in divide and conquer

Missing elements or incorrect output

✅ Handle odd number of arrays by merging last array with empty array or carrying it forward

🧠

Brute Force (Concatenate and Sort)

💡 This approach exists to establish a baseline and to understand the problem constraints. It is simple but inefficient for large inputs.

Intuition

Combine all arrays into one big array and then sort it. Since sorting is a well-known operation, this is the most straightforward way to get the merged sorted array.

Algorithm

1. Create an empty list to hold all elements.
2. Iterate over each array and append all elements to the list.
3. Sort the combined list.
4. Return the sorted list.

💡 The algorithm is easy to understand but inefficient because it ignores the fact that input arrays are already sorted.

</>

Code

def merge_k_sorted_arrays(arrays):
    merged = []
    for arr in arrays:
        merged.extend(arr)
    merged.sort()
    return merged

# Driver code
if __name__ == '__main__':
    arrays = [[1,4,5],[1,3,4],[2,6]]
    print(merge_k_sorted_arrays(arrays))

Line Notes

merged = []Initialize a list to hold all elements from all arrays

for arr in arrays:Iterate over each input array to access its elements

merged.extend(arr)Add all elements of the current array to the merged list

merged.sort()Sort the combined list to get the final sorted array

import java.util.*;
public class MergeKSortedArrays {
    public static List<Integer> mergeKSortedArrays(List<List<Integer>> arrays) {
        List<Integer> merged = new ArrayList<>();
        for (List<Integer> arr : arrays) {
            merged.addAll(arr);
        }
        Collections.sort(merged);
        return merged;
    }
    public static void main(String[] args) {
        List<List<Integer>> arrays = Arrays.asList(
            Arrays.asList(1,4,5),
            Arrays.asList(1,3,4),
            Arrays.asList(2,6)
        );
        System.out.println(mergeKSortedArrays(arrays));
    }
}

Line Notes

List<Integer> merged = new ArrayList<>();Create a list to hold all elements from all arrays

for (List<Integer> arr : arrays)Loop through each input array

merged.addAll(arr);Add all elements of the current array to merged list

Collections.sort(merged);Sort the combined list to get the final sorted array

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> mergeKSortedArrays(const vector<vector<int>>& arrays) {
    vector<int> merged;
    for (const auto& arr : arrays) {
        merged.insert(merged.end(), arr.begin(), arr.end());
    }
    sort(merged.begin(), merged.end());
    return merged;
}

int main() {
    vector<vector<int>> arrays = {{1,4,5},{1,3,4},{2,6}};
    vector<int> result = mergeKSortedArrays(arrays);
    for (int num : result) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<int> merged;Initialize vector to hold all elements

for (const auto& arr : arrays)Iterate over each input array

merged.insert(merged.end(), arr.begin(), arr.end());Append all elements of current array to merged

sort(merged.begin(), merged.end());Sort the combined vector to get the final sorted array

function mergeKSortedArrays(arrays) {
    let merged = [];
    for (let arr of arrays) {
        merged = merged.concat(arr);
    }
    merged.sort((a,b) => a - b);
    return merged;
}

// Driver code
const arrays = [[1,4,5],[1,3,4],[2,6]];
console.log(mergeKSortedArrays(arrays));

Line Notes

let merged = []Initialize an empty array to hold all elements

for (let arr of arrays)Loop through each input array

merged = merged.concat(arr)Concatenate current array elements to merged

merged.sort((a,b) => a - b)Sort the combined array numerically

⏱

Complexity

TimeO(N log N) where N is total number of elements

SpaceO(N) for merged array

We combine all elements into one list of size N and then sort it, which takes O(N log N) time.

💡 If total elements are 100,000, this means roughly 100,000 * log2(100,000) ≈ 1.6 million operations, which can be slow.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large inputs, so we need better methods.

🧠

Better Approach (Using Min Heap to Merge)

💡 This approach leverages a min heap to efficiently merge k sorted arrays by always picking the smallest current element among the arrays.

Intuition

Use a min heap to keep track of the smallest elements from each array. Extract the smallest element and add the next element from the same array to the heap until all elements are processed.

Algorithm

1. Initialize a min heap.
2. Insert the first element of each array into the heap along with array and element indices.
3. While the heap is not empty, extract the smallest element and add it to the result.
4. If the extracted element's array has more elements, insert the next element into the heap.

💡 The heap always contains the next smallest candidates from each array, ensuring efficient merging.

</>

Code

import heapq

def merge_k_sorted_arrays(arrays):
    min_heap = []
    result = []
    # Initialize heap with first element of each array
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(min_heap, (arr[0], i, 0))
    while min_heap:
        val, arr_idx, ele_idx = heapq.heappop(min_heap)
        result.append(val)
        if ele_idx + 1 < len(arrays[arr_idx]):
            next_val = arrays[arr_idx][ele_idx + 1]
            heapq.heappush(min_heap, (next_val, arr_idx, ele_idx + 1))
    return result

# Driver code
if __name__ == '__main__':
    arrays = [[1,4,5],[1,3,4],[2,6]]
    print(merge_k_sorted_arrays(arrays))

Line Notes

min_heap = []Create a min heap to store the smallest elements from each array

for i, arr in enumerate(arrays):Iterate over each array with its index

heapq.heappush(min_heap, (arr[0], i, 0))Push the first element of each array with array and element indices

val, arr_idx, ele_idx = heapq.heappop(min_heap)Pop the smallest element from the heap along with its origin info

import java.util.*;

public class MergeKSortedArrays {
    static class Element implements Comparable<Element> {
        int value, arrIdx, eleIdx;
        Element(int v, int a, int e) { value = v; arrIdx = a; eleIdx = e; }
        public int compareTo(Element other) { return this.value - other.value; }
    }
    public static List<Integer> mergeKSortedArrays(List<List<Integer>> arrays) {
        PriorityQueue<Element> minHeap = new PriorityQueue<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < arrays.size(); i++) {
            if (!arrays.get(i).isEmpty()) {
                minHeap.offer(new Element(arrays.get(i).get(0), i, 0));
            }
        }
        while (!minHeap.isEmpty()) {
            Element curr = minHeap.poll();
            result.add(curr.value);
            if (curr.eleIdx + 1 < arrays.get(curr.arrIdx).size()) {
                int nextVal = arrays.get(curr.arrIdx).get(curr.eleIdx + 1);
                minHeap.offer(new Element(nextVal, curr.arrIdx, curr.eleIdx + 1));
            }
        }
        return result;
    }
    public static void main(String[] args) {
        List<List<Integer>> arrays = Arrays.asList(
            Arrays.asList(1,4,5),
            Arrays.asList(1,3,4),
            Arrays.asList(2,6)
        );
        System.out.println(mergeKSortedArrays(arrays));
    }
}

Line Notes

static class Element implements Comparable<Element>Define a class to hold value and indices for heap ordering

PriorityQueue<Element> minHeap = new PriorityQueue<>();Create a min heap to store elements

minHeap.offer(new Element(arrays.get(i).get(0), i, 0));Add first element of each array to heap

Element curr = minHeap.poll();Extract smallest element from heap

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Element {
    int value, arrIdx, eleIdx;
    Element(int v, int a, int e) : value(v), arrIdx(a), eleIdx(e) {}
    bool operator>(const Element& other) const {
        return value > other.value;
    }
};

vector<int> mergeKSortedArrays(const vector<vector<int>>& arrays) {
    priority_queue<Element, vector<Element>, greater<Element>> minHeap;
    vector<int> result;
    for (int i = 0; i < arrays.size(); i++) {
        if (!arrays[i].empty()) {
            minHeap.emplace(arrays[i][0], i, 0);
        }
    }
    while (!minHeap.empty()) {
        Element curr = minHeap.top();
        minHeap.pop();
        result.push_back(curr.value);
        if (curr.eleIdx + 1 < arrays[curr.arrIdx].size()) {
            minHeap.emplace(arrays[curr.arrIdx][curr.eleIdx + 1], curr.arrIdx, curr.eleIdx + 1);
        }
    }
    return result;
}

int main() {
    vector<vector<int>> arrays = {{1,4,5},{1,3,4},{2,6}};
    vector<int> result = mergeKSortedArrays(arrays);
    for (int num : result) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

struct ElementDefine a struct to hold value and indices for heap comparison

priority_queue<Element, vector<Element>, greater<Element>> minHeap;Create a min heap using greater comparator

minHeap.emplace(arrays[i][0], i, 0);Insert first element of each array into heap

Element curr = minHeap.top();Get smallest element from heap

class Element {
    constructor(value, arrIdx, eleIdx) {
        this.value = value;
        this.arrIdx = arrIdx;
        this.eleIdx = eleIdx;
    }
}

function mergeKSortedArrays(arrays) {
    const minHeap = [];
    const result = [];

    function heapPush(elem) {
        minHeap.push(elem);
        let i = minHeap.length - 1;
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2);
            if (minHeap[parent].value <= minHeap[i].value) break;
            [minHeap[parent], minHeap[i]] = [minHeap[i], minHeap[parent]];
            i = parent;
        }
    }

    function heapPop() {
        const top = minHeap[0];
        const end = minHeap.pop();
        if (minHeap.length > 0) {
            minHeap[0] = end;
            let i = 0;
            while (true) {
                let left = 2 * i + 1;
                let right = 2 * i + 2;
                let smallest = i;
                if (left < minHeap.length && minHeap[left].value < minHeap[smallest].value) smallest = left;
                if (right < minHeap.length && minHeap[right].value < minHeap[smallest].value) smallest = right;
                if (smallest === i) break;
                [minHeap[i], minHeap[smallest]] = [minHeap[smallest], minHeap[i]];
                i = smallest;
            }
        }
        return top;
    }

    for (let i = 0; i < arrays.length; i++) {
        if (arrays[i].length > 0) {
            heapPush(new Element(arrays[i][0], i, 0));
        }
    }

    while (minHeap.length > 0) {
        const curr = heapPop();
        result.push(curr.value);
        if (curr.eleIdx + 1 < arrays[curr.arrIdx].length) {
            heapPush(new Element(arrays[curr.arrIdx][curr.eleIdx + 1], curr.arrIdx, curr.eleIdx + 1));
        }
    }

    return result;
}

// Driver code
const arrays = [[1,4,5],[1,3,4],[2,6]];
console.log(mergeKSortedArrays(arrays));

Line Notes

class ElementDefine a class to hold value and indices for heap elements

function heapPush(elem)Insert element into min heap maintaining heap property

function heapPop()Remove and return smallest element from min heap

for (let i = 0; i < arrays.length; i++)Initialize heap with first element of each array

⏱

Complexity

TimeO(N log k) where N is total elements, k is number of arrays

SpaceO(k) for heap + O(N) for output

Each element is pushed and popped from the heap once. Heap size is at most k, so operations take O(log k).

💡 For 100,000 elements and 100 arrays, this means about 100,000 * log2(100) ≈ 664,000 operations, which is efficient.

Interview Verdict: Accepted and efficient for large inputs

This is the standard optimal approach for merging k sorted arrays in interviews.

🧠

Optimal Approach (Divide and Conquer Merge)

💡 This approach uses divide and conquer to merge pairs of arrays repeatedly, reducing the problem size at each step.

Intuition

Merge arrays in pairs recursively until only one array remains. This reduces the merging problem to repeatedly merging two sorted arrays.

Algorithm

1. If only one array, return it.
2. Pair up arrays and merge each pair into one sorted array.
3. Repeat the process with the merged arrays until only one array remains.
4. Return the final merged array.

💡 This approach reduces the problem size by half each iteration, similar to merge sort.

</>

Code

def merge_two_arrays(arr1, arr2):
    i, j = 0, 0
    merged = []
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            j += 1
    merged.extend(arr1[i:])
    merged.extend(arr2[j:])
    return merged

def merge_k_sorted_arrays(arrays):
    if not arrays:
        return []
    while len(arrays) > 1:
        merged_arrays = []
        for i in range(0, len(arrays), 2):
            arr1 = arrays[i]
            arr2 = arrays[i+1] if i+1 < len(arrays) else []
            merged_arrays.append(merge_two_arrays(arr1, arr2))
        arrays = merged_arrays
    return arrays[0]

# Driver code
if __name__ == '__main__':
    arrays = [[1,4,5],[1,3,4],[2,6]]
    print(merge_k_sorted_arrays(arrays))

Line Notes

def merge_two_arrays(arr1, arr2):Helper function to merge two sorted arrays efficiently

while i < len(arr1) and j < len(arr2):Traverse both arrays to merge in sorted order

merged.extend(arr1[i:])Add remaining elements from arr1 if any

while len(arrays) > 1:Repeat merging pairs until only one array remains

import java.util.*;

public class MergeKSortedArrays {
    public static List<Integer> mergeTwoArrays(List<Integer> arr1, List<Integer> arr2) {
        List<Integer> merged = new ArrayList<>();
        int i = 0, j = 0;
        while (i < arr1.size() && j < arr2.size()) {
            if (arr1.get(i) < arr2.get(j)) {
                merged.add(arr1.get(i++));
            } else {
                merged.add(arr2.get(j++));
            }
        }
        while (i < arr1.size()) merged.add(arr1.get(i++));
        while (j < arr2.size()) merged.add(arr2.get(j++));
        return merged;
    }

    public static List<Integer> mergeKSortedArrays(List<List<Integer>> arrays) {
        if (arrays.isEmpty()) return new ArrayList<>();
        while (arrays.size() > 1) {
            List<List<Integer>> mergedArrays = new ArrayList<>();
            for (int i = 0; i < arrays.size(); i += 2) {
                List<Integer> arr1 = arrays.get(i);
                List<Integer> arr2 = (i + 1 < arrays.size()) ? arrays.get(i + 1) : new ArrayList<>();
                mergedArrays.add(mergeTwoArrays(arr1, arr2));
            }
            arrays = mergedArrays;
        }
        return arrays.get(0);
    }

    public static void main(String[] args) {
        List<List<Integer>> arrays = Arrays.asList(
            Arrays.asList(1,4,5),
            Arrays.asList(1,3,4),
            Arrays.asList(2,6)
        );
        System.out.println(mergeKSortedArrays(arrays));
    }
}

Line Notes

public static List<Integer> mergeTwoArraysHelper method to merge two sorted lists

while (i < arr1.size() && j < arr2.size())Traverse both lists to merge in sorted order

while (i < arr1.size()) merged.add(arr1.get(i++));Add remaining elements from arr1

while (arrays.size() > 1)Repeat merging pairs until one array remains

#include <iostream>
#include <vector>
using namespace std;

vector<int> mergeTwoArrays(const vector<int>& arr1, const vector<int>& arr2) {
    int i = 0, j = 0;
    vector<int> merged;
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) merged.push_back(arr1[i++]);
        else merged.push_back(arr2[j++]);
    }
    while (i < arr1.size()) merged.push_back(arr1[i++]);
    while (j < arr2.size()) merged.push_back(arr2[j++]);
    return merged;
}

vector<int> mergeKSortedArrays(vector<vector<int>> arrays) {
    if (arrays.empty()) return {};
    while (arrays.size() > 1) {
        vector<vector<int>> mergedArrays;
        for (int i = 0; i < arrays.size(); i += 2) {
            vector<int> arr1 = arrays[i];
            vector<int> arr2 = (i + 1 < arrays.size()) ? arrays[i + 1] : vector<int>{};
            mergedArrays.push_back(mergeTwoArrays(arr1, arr2));
        }
        arrays = mergedArrays;
    }
    return arrays[0];
}

int main() {
    vector<vector<int>> arrays = {{1,4,5},{1,3,4},{2,6}};
    vector<int> result = mergeKSortedArrays(arrays);
    for (int num : result) cout << num << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<int> mergeTwoArraysHelper function to merge two sorted vectors

while (i < arr1.size() && j < arr2.size())Traverse both vectors to merge in sorted order

while (i < arr1.size()) merged.push_back(arr1[i++]);Add remaining elements from arr1

while (arrays.size() > 1)Repeat merging pairs until one vector remains

function mergeTwoArrays(arr1, arr2) {
    let i = 0, j = 0;
    const merged = [];
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) merged.push(arr1[i++]);
        else merged.push(arr2[j++]);
    }
    while (i < arr1.length) merged.push(arr1[i++]);
    while (j < arr2.length) merged.push(arr2[j++]);
    return merged;
}

function mergeKSortedArrays(arrays) {
    if (arrays.length === 0) return [];
    while (arrays.length > 1) {
        const mergedArrays = [];
        for (let i = 0; i < arrays.length; i += 2) {
            const arr1 = arrays[i];
            const arr2 = (i + 1 < arrays.length) ? arrays[i + 1] : [];
            mergedArrays.push(mergeTwoArrays(arr1, arr2));
        }
        arrays = mergedArrays;
    }
    return arrays[0];
}

// Driver code
const arrays = [[1,4,5],[1,3,4],[2,6]];
console.log(mergeKSortedArrays(arrays));

Line Notes

function mergeTwoArrays(arr1, arr2)Helper function to merge two sorted arrays

while (i < arr1.length && j < arr2.length)Traverse both arrays to merge in sorted order

while (i < arr1.length) merged.push(arr1[i++]);Add remaining elements from arr1

while (arrays.length > 1)Repeat merging pairs until one array remains

⏱

Complexity

TimeO(N log k) where N is total elements, k is number of arrays

SpaceO(N) for output and temporary merged arrays

Each merge of two arrays takes O(n) time, and we do log k rounds of merging.

💡 This approach is similar in complexity to the heap method but uses pairwise merging instead of a heap.

Interview Verdict: Accepted and efficient alternative to heap

This approach is useful when you want to avoid heap overhead or when arrays are balanced in size.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the min heap approach as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(N log N)	O(N)	No	N/A	Mention only - never code
2. Min Heap	O(N log k)	O(k + N)	No	N/A	Code this approach
3. Divide and Conquer	O(N log k)	O(N)	No	N/A	Mention as alternative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify input size, constraints, and output format.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the min heap approach as the standard efficient solution.Step 4: Optionally mention divide and conquer as an alternative.Step 5: Code the min heap approach carefully, test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Ability to optimize from naive to efficient solutions, understanding of heaps and arrays, and clean coding skills.

Common Follow-ups

• What if arrays are very large and cannot fit in memory? → Use external merge sort or streaming.
• How to merge if arrays are linked lists? → Use similar heap approach with pointers.

💡 These follow-ups test your ability to adapt the solution to real-world constraints and data structures.

🔍

Pattern Recognition

When to Use

1) Multiple sorted arrays/lists given, 2) Need one sorted output, 3) Input arrays are individually sorted, 4) Efficient merging required

Signature Phrases

merge k sorted arrayscombine multiple sorted listsk-way merge

NOT This Pattern When

Sorting a single unsorted array or merging unsorted arrays is a different problem.

Similar Problems

Merge Two Sorted Arrays - simpler version with k=2Merge K Sorted Lists - same pattern but with linked lists

Practice

1. You are given k sorted lists of integers. Your task is to find the smallest range that includes at least one number from each of the k lists. Which algorithmic approach guarantees an optimal solution with efficient time complexity?

easy

A. Use a min-heap to track the current minimum element among the heads of each list while maintaining the current maximum, updating the range as you iterate.

B. Apply a greedy approach by always picking the smallest element from any list and expanding the range until all lists are covered.

C. Sort all elements from all lists into one array and use a dynamic programming approach to find the minimal range covering all lists.

D. Use a brute force approach enumerating all combinations of elements from each list and selecting the minimal range.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding a range that covers at least one element from each of the k sorted lists, minimizing the range size.

2. Step 2: Identify the optimal approach

   Using a min-heap to track the smallest current element from each list and maintaining the maximum element seen so far allows efficient updates of the range while iterating through the lists.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap approach efficiently tracks min and max for optimal range [OK]

Hint: Min-heap tracks min and max for optimal range [OK]

Common Mistakes:

• Thinking brute force is feasible for large k
• Assuming greedy picking smallest element always works
• Confusing DP applicability here

2. You need to generate the nth number whose prime factors come only from a given list of k primes. Which approach guarantees an optimal solution with time complexity better than brute force?

easy

A. Use a dynamic programming approach with a 2D table tracking multiples of each prime and the current ugly number index.

B. Use brute force by generating all multiples of primes and checking if they are super ugly numbers.

C. Use a greedy approach that picks the smallest prime factor at each step without tracking duplicates.

D. Use a min-heap to merge sorted sequences generated by multiplying each prime with previously found ugly numbers (k-way merge).

Solution

1. Step 1: Understand problem constraints

   The problem requires generating numbers whose prime factors are limited to a given set of primes, efficiently finding the nth such number.

2. Step 2: Identify the optimal pattern

   Using a min-heap to merge k sorted sequences (each sequence generated by multiplying a prime with previously found ugly numbers) efficiently produces the sequence in ascending order without duplicates.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min-heap merges k sorted lists in O(n log k) time [OK]

Hint: Min-heap merges multiple sorted sequences efficiently [OK]

Common Mistakes:

• Greedy approach misses duplicates and ordering
• Brute force is too slow for large n
• DP without heap is less efficient

3. What is the time complexity of the optimal approach that assigns n jobs to K machines using event sorting and a single min-heap to track running jobs?

medium

A. O(n * K) because each job may check all machines for availability.

B. O(n log n) because sorting jobs dominates and heap operations are constant time.

C. O(n log K) because jobs are sorted and each heap operation on K machines costs log K.

D. O(n + K) because heap operations are amortized to constant time.

Solution

1. Step 1: Analyze sorting step

   Sorting jobs by start time takes O(n log n).

2. Step 2: Analyze heap operations

   Each job causes at most one pop and one push on the min-heap of size at most K, costing O(log K) per job.

3. Step 3: Combine complexities

   Since K ≤ n generally, O(n log n) sorting and O(n log K) heap operations combine to O(n log n). But since K ≤ n, and the problem emphasizes K machines, the heap operations dominate as O(n log K).

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Heap operations scale with log K, sorting with log n; overall O(n log K) [OK]

Hint: Heap operations cost log K, not linear K [OK]

Common Mistakes:

• Confusing heap size as n instead of K
• Ignoring sorting cost or assuming heap ops are constant time
• Assuming linear scan per job leads to O(nK)

4. The following code attempts to find the smallest range covering k sorted lists using a min-heap. Identify the line containing the subtle bug that can cause incorrect results or runtime errors.

medium

A. Line popping the smallest element from the heap

B. Line checking if ele_idx + 1 == len(nums[list_idx]) to break the loop

C. Line updating current_max after pushing next_val into the heap

D. Line initializing min_range to float('inf')

Solution

1. Step 1: Identify the role of current_max

   current_max tracks the maximum element in the current window; it must be updated when pushing a new element.

2. Step 2: Locate missing update

   The code comment indicates current_max is not updated after pushing next_val, causing incorrect range calculation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Without updating current_max, range may be underestimated or incorrect [OK]

Hint: Always update current_max after pushing new heap element [OK]

Common Mistakes:

• Forgetting to update current_max after pushing new element
• Breaking loop too early or too late
• Misusing heap pop or initialization

5. Suppose jobs can be reused multiple times (i.e., the same job can be assigned repeatedly), and you want to assign jobs to machines minimizing start delays as before. Which modification to the optimal algorithm is necessary to handle this scenario correctly?

hard

A. No change needed; the existing algorithm handles reuse naturally by sorting jobs once and assigning sequentially.

B. Sort jobs by duration instead of start time to prioritize shorter jobs for reuse.

C. Use a brute force approach checking all possible assignments since reuse breaks heap assumptions.

D. Maintain a priority queue of job instances and re-insert jobs after completion to simulate reuse, updating start times accordingly.

Solution

1. Step 1: Understand job reuse impact

   Reusing jobs means after a job finishes, it can be assigned again, so jobs are not fixed once but can appear multiple times.

2. Step 2: Modify algorithm to handle reuse

   Maintain a priority queue of job instances with their next available start times. After a job finishes, re-insert it with updated start time to simulate reuse.

3. Step 3: Why other options fail

   No change ignores reuse; brute force is inefficient; sorting by duration ignores start times and scheduling constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Re-inserting jobs after completion models reuse correctly [OK]

Hint: Re-insert jobs with updated start times to simulate reuse [OK]

Common Mistakes:

• Assuming reuse needs no algorithm change
• Switching sort order breaks scheduling correctness
• Using brute force is inefficient and unnecessary