Find Median of K Sorted Arrays

📋

Find Median of K Sorted Arrays

Edge cases:

</>

IDE

def find_median_k_sorted_arrays(arrays: list[list[int]]) -> float:public double findMedianKSortedArrays(List<List<Integer>> arrays)double findMedianKSortedArrays(const vector<vector<int>>& arrays)function findMedianKSortedArrays(arrays)

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

class Solution {
    public double findMedianKSortedArrays(List<List<Integer>> arrays) {
        // Write your solution here
        return 0.0;
    }
}

#include <vector>
using namespace std;

double findMedianKSortedArrays(const vector<vector<int>>& arrays) {
    // Write your solution here
    return 0.0;
}

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

Common Bugs to Avoid

Wrong: Median of medians of individual arraysUsing median of each array and averaging instead of global median.✅ Implement global counting of elements <= mid using binary search or k-way merge.

Wrong: Wrong median for even total length (e.g., returning one middle element only)Ignoring averaging two middle elements when total length is even.✅ Check total length parity and average two middle elements if even.

Wrong: Crash or invalid output on empty inputNot handling empty arrays or no elements case.✅ Add checks for empty input and raise error or return null.

Wrong: Off-by-one median due to incorrect binary search boundariesIncorrect inclusive/exclusive conditions in binary search counting.✅ Adjust binary search to count elements <= mid correctly and update boundaries accordingly.

Wrong: TLE on large inputsUsing brute force merge or sorting all elements.✅ Use binary search on value range or min-heap k-way merge for better complexity.

✓

Test Cases

Handle empty and minimal inputs carefully to avoid runtime errors.

Watch out for common algorithmic traps like greedy median and off-by-one errors.

Focus on optimizing your approach to handle large inputs efficiently.

t1_01basic

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

Expected5

⏱ Performance - must finish in 2000ms

Combined sorted array is [1,2,3,4,5,6,7,8,9], median is 5 (middle element).

💡 Think about merging K sorted arrays into one sorted list.

💡 Use a min-heap to efficiently merge arrays and find the median.

💡 The median is the middle element if odd total length, else average of two middle elements.

Why it failed: Incorrect median output: likely incorrect merging or median index calculation. Fix by correctly merging arrays or using binary search on value range.

✓ Correct median found using proper merging or binary search.

t1_02basic

Input{"arrays":[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]}

Expected6.5

⏱ Performance - must finish in 2000ms

Combined sorted array is [1,2,3,4,5,6,7,8,9,10,11,12], median is average of 6 and 7 = 6.5.

💡 Count total elements to determine if median is single element or average of two.

💡 Use binary search on value range to count elements less or equal to mid.

💡 Median is average of elements at positions n/2 and n/2+1 for even n.

Why it failed: Median calculation error: likely ignoring even length median averaging. Fix by averaging two middle elements when total count is even.

✓ Median correctly computed as average for even total length.

t2_01edge

Input{"arrays":[]}

Expectednull

⏱ Performance - must finish in 2000ms

No arrays given, median undefined; function should handle empty input gracefully.

💡 Check if input arrays list is empty before processing.

💡 Return error or null if no elements exist to find median.

💡 Raise exception or return null to indicate no median possible.

Why it failed: Function crashes or returns invalid median on empty input. Fix by adding check for empty input and handle accordingly.

✓ Properly handles empty input by returning null or raising error.

t2_02edge

Input{"arrays":[[]]}

Expectednull

⏱ Performance - must finish in 2000ms

Single empty array means no elements; median undefined.

💡 Check if all arrays are empty before computing median.

💡 Return null or error if total elements count is zero.

💡 Avoid processing empty arrays to prevent errors.

Why it failed: Fails on single empty array input by returning wrong median or crashing. Fix by checking total element count before median calculation.

✓ Correctly returns null or error for single empty array.

t2_03edge

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

Expected5

⏱ Performance - must finish in 2000ms

Single element array median is the element itself.

💡 For single element total, median is that element.

💡 Check total length before median calculation.

💡 Return the only element when total length is one.

Why it failed: Incorrect median for single element input. Fix by returning the element directly when total length is one.

✓ Correctly returns the single element as median.

t2_04edge

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

Expected1

⏱ Performance - must finish in 2000ms

All elements identical; median is that identical value.

💡 Duplicates do not affect median value if all are same.

💡 Check counting logic handles identical elements correctly.

💡 Median should be the identical element value.

Why it failed: Median incorrect due to mishandling duplicates. Fix by counting all elements properly including duplicates.

✓ Correct median returned for identical elements.

t3_01corner

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

Expected2

⏱ Performance - must finish in 2000ms

Duplicates present; combined sorted array has many 2s; median is 2.

💡 Duplicates affect median position counting.

💡 Use counting of elements <= mid carefully to handle duplicates.

💡 Binary search on value range must count duplicates correctly.

Why it failed: Median off due to incorrect counting of duplicates. Fix by counting all elements <= mid including duplicates in binary search.

✓ Correct median found accounting for duplicates.

t3_02corner

Input{"arrays":[[1,3,5],[2,4,6],[7,8,9],[10,11,12]]}

Expected6.5

⏱ Performance - must finish in 2000ms

Greedy approach picking medians of individual arrays fails; combined median is 6.5.

💡 Median of medians of individual arrays is not overall median.

💡 Use global binary search or k-way merge instead of greedy per-array median.

💡 Count elements <= mid globally to find correct median.

Why it failed: Greedy median of medians approach returns wrong median. Fix by using global counting or k-way merge for median.

✓ Global median correctly computed, avoiding greedy trap.

t3_03corner

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

Expected2

⏱ Performance - must finish in 2000ms

Off-by-one errors in binary search can cause wrong median; median is 2.

💡 Binary search on value range requires careful mid counting.

💡 Check inclusive/exclusive conditions when counting elements <= mid.

💡 Adjust binary search boundaries to avoid off-by-one errors.

Why it failed: Off-by-one error in binary search causes wrong median. Fix by correctly handling mid and count comparisons inclusive of mid.

✓ Binary search correctly finds median with proper boundary handling.

t4_01performance

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

Expectednull

⏱ Performance - must finish in 2000ms

n=10 arrays each with 100 elements (total 1000). O(N log K) or O(K log M log N) needed to pass in 2s.

💡 Brute force merging all elements will TLE here.

💡 Use binary search on value range with counting to achieve O(K log M log N).

💡 Min-heap k-way merge is better than brute force but may still be slow for max constraints.

Why it failed: TLE due to brute force or naive merging approach. Fix by implementing binary search on value range or efficient heap-based merge.

✓ Efficient algorithm passes within time limit.

Practice

1. Given the following code for finding k pairs with smallest sums, what is the returned result when called with nums1 = [1,7,11], nums2 = [2,4,6], and k = 3?

easy

A. [[1, 2], [1, 4], [1, 6]]

B. [[1, 2], [7, 2], [1, 4]]

C. [[1, 2], [7, 2], [7, 4]]

D. [[1, 2], [1, 4], [7, 2]]

Solution

1. Step 1: Initialize min-heap with pairs (nums1[i] + nums2[0])

   Push (1+2,0,0), (7+2,1,0), (11+2,2,0) -> heap = [(3,0,0),(9,1,0),(13,2,0)]

2. Step 2: Extract k=3 pairs

   Pop (3,0,0) -> result [[1,2]], push (1+4,0,1) -> heap [(7,0,1),(9,1,0),(13,2,0)] Pop (7,0,1) -> result [[1,2],[1,4]], push (1+6,0,2) -> heap [(7,1,0),(13,2,0),(7,0,2)] Pop (7,1,0) -> result [[1,2],[1,4],[7,2]]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches expected output from code trace [OK]

Hint: Heap pops smallest sum pairs in order [OK]

Common Mistakes:

• Off-by-one in indexing nums2
• Wrong order of pairs in result
• Confusing heap push/pop order

2. Consider the following buggy code for finding k pairs with smallest sums. Which line contains the subtle bug that can cause incorrect results or runtime errors?

medium

A. Line 16: Condition 'if j + 1 <= n2' before pushing new pair

B. Line 11: Looping up to min(k, n1) to initialize heap

C. Line 14: Popping from the min-heap

D. Line 7: Checking if nums1 or nums2 is empty

Solution

1. Step 1: Analyze boundary condition in line 16

   The condition 'if j + 1 <= n2' allows j+1 to be equal to n2, which is out of bounds for nums2 indexing.

2. Step 2: Correct condition

   It should be 'if j + 1 < n2' to prevent index out of range errors and missing pairs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Off-by-one error in boundary check causes runtime or logic errors [OK]

Hint: Check array index boundaries carefully [OK]

Common Mistakes:

• Off-by-one in array indexing
• Incorrect heap initialization
• Ignoring empty input checks

3. What is the time complexity of the binary search approach that finds the k-th smallest sum in two sorted arrays of lengths n and m, assuming the sums range between minSum and maxSum?

medium

A. O((n + m) * log(maxSum - minSum))

B. O(n * m * log(maxSum - minSum))

C. O(n * log m * log(maxSum - minSum))

D. O(n * m)

Solution

1. Step 1: Analyze countPairs complexity

   countPairs runs in O(n + m) because j only moves backward once across all i.

2. Step 2: Analyze binary search iterations

   Binary search runs O(log(maxSum - minSum)) times.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Combined complexity is O((n + m) * log(maxSum - minSum)) [OK]

Hint: countPairs uses two-pointer linear scan, not nested loops [OK]

Common Mistakes:

• Assuming countPairs is O(n*m)
• Confusing n and m in complexity

4. Suppose the problem changes so that elements from the arrays can be reused multiple times to form sums (i.e., pairs can include the same element multiple times). Which modification to the binary search approach is necessary to correctly find the k-th smallest sum?

hard

A. No modification needed; reuse does not affect counting pairs.

B. Use a min-heap approach with a visited set to handle duplicates and reuse correctly.

C. Modify countPairs to count pairs with replacement by resetting pointer j for each i.

D. Use binary search but countPairs must be replaced with a formula counting sums with repetition.

Solution

1. Step 1: Understand reuse effect on counting

   With reuse allowed, pairs are not limited to unique indices; counting must consider all j for each i.

2. Step 2: Modify countPairs

   Resetting j for each i allows counting all pairs with sums ≤ mid including repeated elements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting j ensures correct counting with reuse [OK]

Hint: Reusing elements breaks monotonic pointer j; must reset per i [OK]

Common Mistakes:

• Assuming original countPairs works with reuse
• Using heap without visited set causes duplicates

5. Suppose the problem changes: now you want to find the nth ugly number but you can reuse the same ugly number multiple times in generating new numbers (i.e., duplicates allowed). Which modification to the min-heap approach correctly handles this variant without losing correctness or efficiency?

hard

A. Remove the 'seen' set entirely and push all generated numbers into the heap, allowing duplicates.

B. Keep the 'seen' set but reset it after every iteration to allow reuse of numbers in the next iteration.

C. Use a counter map to track how many times each number is generated and only push if count is below a threshold.

D. Keep the 'seen' set as is to avoid duplicates, since duplicates do not affect correctness or efficiency.

Solution

1. Step 1: Understand the variant allowing duplicates

   Allowing reuse means duplicates are valid and should be generated and processed multiple times.

2. Step 2: Modify the algorithm accordingly

   Removing the 'seen' set allows duplicates to be pushed and popped, correctly reflecting the new problem constraints.

3. Step 3: Consider efficiency

   Though duplicates increase heap size, this is necessary to correctly generate all numbers under the new rules.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing 'seen' allows duplicates as required [OK]

Hint: Allow duplicates by removing 'seen' when reuse is allowed [OK]

Common Mistakes:

• Keeping 'seen' and missing duplicates
• Resetting 'seen' incorrectly
• Using counters unnecessarily