Merge K Sorted Arrays

📋

Merge K Sorted Arrays

Edge cases:

</>

IDE

def merge_k_sorted_arrays(arrays: list[list[int]]) -> list[int]:public int[] mergeKSortedArrays(int[][] arrays)vector<int> mergeKSortedArrays(vector<vector<int>>& arrays)function mergeKSortedArrays(arrays)

def merge_k_sorted_arrays(arrays):
    # Write your solution here
    pass

class Solution {
    public int[] mergeKSortedArrays(int[][] arrays) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> mergeKSortedArrays(vector<vector<int>>& arrays) {
    // Write your solution here
    return {};
}

function mergeKSortedArrays(arrays) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,2,3,4,5,6]Merging arrays pairwise greedily without global ordering causes incorrect output.✅ Use a min heap to merge all arrays simultaneously, pushing first elements of each array and popping smallest repeatedly.

Wrong: [1,2,3,4,5]Removing duplicates or treating arrays as sets instead of preserving all elements.✅ Push all elements from all arrays into the heap, preserving duplicates exactly.

Wrong: [1,1,3,4,5,6]Off-by-one error in index tracking causes missing elements.✅ After popping from heap, increment index correctly and check bounds before pushing next element.

Wrong: TLE or timeoutUsing brute force concatenation and sorting instead of min heap merge.✅ Implement min heap based k-way merge with O(N log k) complexity.

Wrong: Exception or crashNot handling empty input or empty arrays properly.✅ Check for empty input and skip empty arrays before processing.

✓

Test Cases

Try testing your code with empty arrays and single-element arrays to ensure base cases are handled.

Consider cases with duplicates and verify your merge logic does not remove or reorder elements incorrectly.

Focus on algorithmic complexity; brute force sorting will time out on large inputs.

t1_01basic

Input{"arrays":[[1,4,5],[1,3,4],[2,6]]}

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

⏱ Performance - must finish in 2000ms

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

💡 Think about using a min heap to always pick the smallest current element.

💡 Track the indices of arrays and elements to know which element to push next into the heap.

💡 Push the first element of each array into the heap, then pop the smallest and push the next element from that array.

Why it failed: Basic case failed - likely not merging arrays correctly or not maintaining sorted order. Fix by using a min heap to always extract the smallest element among current heads.

✓ Core merging logic with min heap is correct.

t1_02basic

Input{"arrays":[[-5,0,3],[2,2,2],[1,4,6,8]]}

Expected[-5,0,1,2,2,2,3,4,6,8]

⏱ Performance - must finish in 2000ms

Merging arrays with duplicates and varying lengths into one sorted array.

💡 Duplicates should appear in the output as many times as they appear in input arrays.

💡 Ensure your heap handles equal elements correctly and maintains stable ordering.

💡 After popping from heap, push the next element from the same array until all arrays are exhausted.

Why it failed: Failed to handle duplicates or array boundaries correctly. Fix by pushing next elements from the same array after popping from heap until all arrays are merged.

✓ Duplicates and varying lengths handled correctly.

t2_01edge

Input{"arrays":[[]]}

Expected[]

⏱ Performance - must finish in 2000ms

Single empty array input should return an empty array.

💡 Check if your code handles empty arrays without errors.

💡 Make sure you don't push elements from empty arrays into the heap.

💡 Return empty list if all arrays are empty or contain no elements.

Why it failed: Code crashes or returns non-empty output on empty arrays. Fix by skipping empty arrays and returning empty list if no elements.

✓ Empty single array handled correctly.

t2_02edge

Input{"arrays":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input list (no arrays) should return an empty array.

💡 Check if your code handles zero arrays gracefully.

💡 Avoid accessing arrays[0] or similar without checking length.

💡 Return empty list immediately if input is empty.

Why it failed: Code throws index error or returns wrong output on empty input list. Fix by checking if input is empty before processing.

✓ Empty input list handled correctly.

t2_03edge

Input{"arrays":[[1]]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single array with one element should return that element.

💡 Check if your code handles single-element arrays correctly.

💡 Ensure the element is pushed and popped correctly from the heap.

💡 Return the single element as the merged output.

Why it failed: Code fails to return single element correctly or returns empty. Fix by pushing first element of each array into heap regardless of length.

✓ Single element array handled correctly.

t2_04edge

Input{"arrays":[[2,2,2],[2,2],[2]]}

Expected[2,2,2,2,2,2]

⏱ Performance - must finish in 2000ms

All elements identical across arrays should appear in output preserving duplicates.

💡 Duplicates must be preserved exactly as in input arrays.

💡 Ensure heap handles equal elements correctly.

💡 Push all elements from all arrays into the heap.

Why it failed: Code removes duplicates or merges incorrectly treating arrays as sets. Fix by pushing all elements and preserving duplicates.

✓ All identical elements merged correctly.

t3_01corner

Input{"arrays":[[1,3,5],[2,4,6],[0,7,8]]}

Expected[0,1,2,3,4,5,6,7,8]

⏱ Performance - must finish in 2000ms

Test to catch greedy approach that merges arrays pairwise incorrectly.

💡 Beware of merging arrays two at a time greedily; it may not be efficient or correct.

💡 Use a min heap to merge all arrays simultaneously to maintain global order.

💡 Push first element of each array into a min heap and pop the smallest repeatedly.

Why it failed: Greedy pairwise merging leads to incorrect order or inefficiency. Fix by using a min heap to merge all arrays at once.

✓ Global min heap merge approach confirmed.

t3_02corner

Input{"arrays":[[1,1,1],[1,1],[1]]}

Expected[1,1,1,1,1,1]

⏱ Performance - must finish in 2000ms

Test to catch confusion between 0/1 and unbounded merges; duplicates must be preserved exactly.

💡 Duplicates must appear as many times as they occur in input arrays.

💡 Do not remove duplicates or treat arrays as sets.

💡 Push all elements from all arrays into the heap respecting their counts.

Why it failed: Code removes duplicates or merges incorrectly treating arrays as sets. Fix by pushing all elements and preserving duplicates.

✓ Duplicates preserved correctly.

t3_03corner

Input{"arrays":[[-10,-5,0],[0,5,10],[10,15,20]]}

Expected[-10,-5,0,0,5,10,10,15,20]

⏱ Performance - must finish in 2000ms

Test to catch off-by-one errors in index tracking when pushing next elements.

💡 Ensure you increment the index correctly after popping an element from heap.

💡 Do not skip or repeat elements due to incorrect index updates.

💡 Push next element from the same array only if index is within bounds.

Why it failed: Off-by-one error causes missing or duplicated elements. Fix by carefully updating indices and checking bounds before pushing next element.

✓ Index tracking and bounds checking correct.

t4_01performance

Input{"arrays":[[0,10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990],[5,15,25,35,45,55,65,75,85,95,105,115,125,135,145,155,165,175,185,195,205,215,225,235,245,255,265,275,285,295,305,315,325,335,345,355,365,375,385,395,405,415,425,435,445,455,465,475,485,495,505,515,525,535,545,555,565,575,585,595,605,615,625,635,645,655,665,675,685,695,705,715,725,735,745,755,765,775,785,795,805,815,825,835,845,855,865,875,885,895,905,915,925,935,945,955,965,975,985,995],[2,12,22,32,42,52,62,72,82,92,102,112,122,132,142,152,162,172,182,192,202,212,222,232,242,252,262,272,282,292,302,312,322,332,342,352,362,372,382,392,402,412,422,432,442,452,462,472,482,492,502,512,522,532,542,552,562,572,582,592,602,612,622,632,642,652,662,672,682,692,702,712,722,732,742,752,762,772,782,792,802,812,822,832,842,852,862,872,882,892,902,912,922,932,942,952,962,972,982,992],[7,17,27,37,47,57,67,77,87,97,107,117,127,137,147,157,167,177,187,197,207,217,227,237,247,257,267,277,287,297,307,317,327,337,347,357,367,377,387,397,407,417,427,437,447,457,467,477,487,497,507,517,527,537,547,557,567,577,587,597,607,617,627,637,647,657,667,677,687,697,707,717,727,737,747,757,767,777,787,797,807,817,827,837,847,857,867,877,887,897,907,917,927,937,947,957,967,977,987,997],[1,11,21,31,41,51,61,71,81,91,101,111,121,131,141,151,161,171,181,191,201,211,221,231,241,251,261,271,281,291,301,311,321,331,341,351,361,371,381,391,401,411,421,431,441,451,461,471,481,491,501,511,521,531,541,551,561,571,581,591,601,611,621,631,641,651,661,671,681,691,701,711,721,731,741,751,761,771,781,791,801,811,821,831,841,851,861,871,881,891,901,911,921,931,941,951,961,971,981,991],[3,13,23,33,43,53,63,73,83,93,103,113,123,133,143,153,163,173,183,193,203,213,223,233,243,253,263,273,283,293,303,313,323,333,343,353,363,373,383,393,403,413,423,433,443,453,463,473,483,493,503,513,523,533,543,553,563,573,583,593,603,613,623,633,643,653,663,673,683,693,703,713,723,733,743,753,763,773,783,793,803,813,823,833,843,853,863,873,883,893,903,913,923,933,943,953,963,973,983,993],[6,16,26,36,46,56,66,76,86,96,106,116,126,136,146,156,166,176,186,196,206,216,226,236,246,256,266,276,286,296,306,316,326,336,346,356,366,376,386,396,406,416,426,436,446,456,466,476,486,496,506,516,526,536,546,556,566,576,586,596,606,616,626,636,646,656,666,676,686,696,706,716,726,736,746,756,766,776,786,796,806,816,826,836,846,856,866,876,886,896,906,916,926,936,946,956,966,976,986,996],[4,14,24,34,44,54,64,74,84,94,104,114,124,134,144,154,164,174,184,194,204,214,224,234,244,254,264,274,284,294,304,314,324,334,344,354,364,374,384,394,404,414,424,434,444,454,464,474,484,494,504,514,524,534,544,554,564,574,584,594,604,614,624,634,644,654,664,674,684,694,704,714,724,734,744,754,764,774,784,794,804,814,824,834,844,854,864,874,884,894,904,914,924,934,944,954,964,974,984,994],[8,18,28,38,48,58,68,78,88,98,108,118,128,138,148,158,168,178,188,198,208,218,228,238,248,258,268,278,288,298,308,318,328,338,348,358,368,378,388,398,408,418,428,438,448,458,468,478,488,498,508,518,528,538,548,558,568,578,588,598,608,618,628,638,648,658,668,678,688,698,708,718,728,738,748,758,768,778,788,798,808,818,828,838,848,858,868,878,888,898,908,918,928,938,948,958,968,978,988,998]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with k=10 arrays each with 100 elements, total 1000 elements. Must complete in O(N log k) time within 2 seconds.

💡 Use a min heap to merge k sorted arrays efficiently.

💡 Avoid concatenating all arrays and sorting, which is O(N log N).

💡 Heap operations are O(log k), so total complexity is O(N log k).

Why it failed: TLE due to using brute force concatenation and sorting (O(N log N)) instead of min heap merge (O(N log k)). Fix by implementing min heap based k-way merge.

✓ Efficient O(N log k) complexity confirmed.

Practice

1. Consider the following Python code implementing the optimal binary search approach to find the median of K sorted arrays. Given arrays = [[1,3,5], [2,4,6], [0,7,8]], what is the value of median1 after the binary search loop completes?

easy

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Calculate total length and median indices

   Total length = 3 + 3 + 3 = 9, so mid1 = (9-1)//2 = 4.

2. Step 2: Perform binary search on value range [0,8]

   Counting elements ≤ mid at each step narrows down to the smallest number with count > 4, which is 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Median of combined sorted array [0,1,2,3,4,5,6,7,8] is 4 [OK]

Hint: Median index 4 corresponds to value 4 in combined arrays [OK]

Common Mistakes:

• Off-by-one in median index
• Miscounting elements ≤ mid
• Confusing median1 and median2

2. Given the following code snippet, what is the final output when called with nums1 = [1,7,11], nums2 = [2,4,6], and k = 3?

def countPairs(nums1, nums2, mid):
    count = 0
    j = len(nums2) - 1
    for i in range(len(nums1)):
        while j >= 0 and nums1[i] + nums2[j] > mid:
            j -= 1
        count += (j + 1)
    return count

def kthSmallestSum(nums1, nums2, k):
    low = nums1[0] + nums2[0]
    high = nums1[-1] + nums2[-1]
    while low < high:
        mid = (low + high) // 2
        if countPairs(nums1, nums2, mid) < k:
            low = mid + 1
        else:
            high = mid
    return low

print(kthSmallestSum(nums1, nums2, k))

easy

A. 6

B. 7

C. 8

D. 9

Solution

1. Step 1: Trace binary search bounds

   low=3 (1+2), high=17 (11+6). Mid values checked: 10, 6, 4, 3, 7.

2. Step 2: Count pairs ≤ mid

   For mid=7, countPairs returns 3 pairs ≤7, which matches k=3, so high=7.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected k-th smallest sum [OK]

Hint: Binary search narrows sum range to find k-th smallest sum [OK]

Common Mistakes:

• Off-by-one in binary search bounds
• Miscounting pairs in countPairs

3. 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

4. What is the time complexity of the optimal binary search on value range approach to find the median of K sorted arrays, each of average length N, with value range size M?

medium

A. O(K * log M * log N)

B. O(K * N * log M)

C. O(K * N * log N)

D. O(K * log N * log M)

Solution

1. Step 1: Analyze binary search outer loop

   Binary search on value range M takes O(log M) steps.

2. Step 2: Analyze counting elements ≤ mid

   Counting uses binary search on each array of length N, costing O(log N) per array, total O(K log N).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(K log M log N) [OK]

Hint: Counting uses binary search per array, not linear scan [OK]

Common Mistakes:

• Assuming linear scan over arrays (O(KN))
• Confusing N and M in complexity
• Ignoring binary search inside counting

5. 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)