Median of Two Sorted Arrays

📋

Median of Two Sorted Arrays

Edge cases:

</>

IDE

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:public double findMedianSortedArrays(int[] nums1, int[] nums2)double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)function findMedianSortedArrays(nums1, nums2)

def findMedianSortedArrays(nums1, nums2):
    # Write your solution here
    pass

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Write your solution here
        return 0.0;
    }
}

#include <vector>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    // Write your solution here
    return 0.0;
}

function findMedianSortedArrays(nums1, nums2) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1.0Returning first element of merged arrays without proper median calculation.✅ Calculate median based on combined length parity; do not return first element blindly.

Wrong: 3.0Incorrect median for even length arrays by returning middle element instead of average of two middles.✅ For even length, return average of merged[n//2 - 1] and merged[n//2].

Wrong: 2.5Failing to handle empty array input, defaulting to median of non-empty array incorrectly.✅ Check for empty arrays and return median of non-empty array directly.

Wrong: 4.0Off-by-one error in partition indices causing wrong median in binary search approach.✅ Adjust partition indices to ensure left and right halves are balanced and conditions hold.

Wrong: TLEUsing O(m+n) merge approach on large inputs causing time limit exceeded.✅ Implement binary search partition approach with O(log(min(m,n))) time complexity.

✓

Test Cases

Try testing your code with empty and single element arrays to catch base case bugs.

Focus on binary search partition logic and handling edge cases like duplicates and negatives.

Optimize your solution to O(log(min(m,n))) time to handle large inputs efficiently.

t1_01basic

Input{"nums1":[1,3],"nums2":[2]}

Expected2

⏱ Performance - must finish in 2000ms

Merged array is [1, 2, 3], median is 2

💡 Think about merging two sorted arrays and finding the middle element(s).

💡 Consider the combined length and whether it's odd or even to find median.

💡 If odd length, median is middle element; if even, average two middle elements.

Why it failed: Incorrect median output; likely failed to merge arrays correctly or miscalculated median index. Fix by correctly merging and handling odd/even length median calculation.

✓ Correctly merged arrays and computed median for odd combined length.

t1_02basic

Input{"nums1":[1,2],"nums2":[3,4]}

Expected2.5

⏱ Performance - must finish in 2000ms

Merged array is [1, 2, 3, 4], median is (2 + 3) / 2 = 2.5

💡 Check how median is computed when total length is even.

💡 Remember to average the two middle elements for even length arrays.

💡 Ensure indices for middle elements are correctly identified and averaged.

Why it failed: Median calculation incorrect for even total length; likely did not average middle two elements properly. Fix by averaging merged[n//2 - 1] and merged[n//2].

✓ Correctly handled even length median calculation.

t2_01edge

Input{"nums1":[],"nums2":[1]}

Expected1

⏱ Performance - must finish in 2000ms

One array empty, median is median of non-empty array [1]

💡 What if one array is empty? Median is from the other array.

💡 Check for empty input arrays before merging.

💡 Return median of the non-empty array directly if the other is empty.

Why it failed: Failed to handle empty array input; likely tried to merge both arrays blindly. Fix by checking for empty arrays and returning median of non-empty array.

✓ Correctly handled empty array input by returning median of non-empty array.

t2_02edge

Input{"nums1":[2],"nums2":[]}

Expected2

⏱ Performance - must finish in 2000ms

Single element in one array, other empty; median is that element

💡 Single element arrays are a base case for median calculation.

💡 Check if one array is empty and the other has one element.

💡 Return that single element as the median.

Why it failed: Incorrect median for single element with empty other array; fix by returning the single element directly when other array is empty.

✓ Correctly returned median for single element array with empty other array.

t2_03edge

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

Expected4.5

⏱ Performance - must finish in 2000ms

Arrays of equal size, median is average of 4 and 5 in merged array

💡 Check median calculation when arrays have equal length.

💡 Merged array length is even; average middle two elements.

💡 Ensure correct indexing for middle elements in merged array.

Why it failed: Median calculation off by one index for even length arrays; fix by averaging merged[n//2 - 1] and merged[n//2].

✓ Correctly computed median for equal sized arrays.

t2_04edge

Input{"nums1":[1,1,1,1],"nums2":[1,1,1,1]}

Expected1

⏱ Performance - must finish in 2000ms

All elements identical; median is that identical value

💡 Check if duplicates affect median calculation.

💡 Median should be the repeated value if all elements are identical.

💡 Ensure no off-by-one errors when all values are the same.

Why it failed: Incorrect median with all identical elements; fix by correctly handling duplicates and median index calculation.

✓ Correctly handled median with all identical elements.

t3_01corner

Input{"nums1":[1,3,5],"nums2":[2,4,6,8,10]}

Expected4.5

⏱ Performance - must finish in 2000ms

Arrays of different sizes; median is 5 in merged array [1, 2, 3, 4, 5, 6, 8, 10]

💡 Consider arrays of different lengths and how to partition them.

💡 Binary search partition approach requires careful index calculation.

💡 Check partition indices to ensure left and right halves are balanced.

Why it failed: Incorrect median due to wrong partition indices in binary search; fix by adjusting partition logic to maintain balanced halves.

✓ Correctly handled different sized arrays with binary search partition.

t3_02corner

Input{"nums1":[1,2,2],"nums2":[2,2,3]}

Expected2

⏱ Performance - must finish in 2000ms

Arrays with duplicates; median accounts for duplicates correctly

💡 Duplicates can affect partition boundaries.

💡 Ensure binary search handles equal elements correctly.

💡 Check conditions for partition edges with duplicates.

Why it failed: Median incorrect due to mishandling duplicates in partition; fix by using <= and >= comparisons properly in partition checks.

✓ Correctly handled duplicates in median calculation.

t3_03corner

Input{"nums1":[-5,3,6,12,15],"nums2":[-12,-10,-6,-3,4,10]}

Expected3

⏱ Performance - must finish in 2000ms

Arrays with negative and positive numbers; median is 3

💡 Negative numbers affect partition comparisons.

💡 Check boundary conditions when arrays contain negative values.

💡 Ensure partition logic correctly compares elements across sign boundaries.

Why it failed: Median wrong due to incorrect handling of negative values in partition; fix by careful comparison of partition edges including negatives.

✓ Correctly handled negative and positive numbers in median calculation.

t4_01performance

Input{"nums1":[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],"nums2":[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]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input arrays with n=100 each; O(log(min(m,n))) solution must complete within 2 seconds

💡 Brute force merge is O(m+n) and too slow for large inputs.

💡 Use binary search on smaller array to find correct partition.

💡 Optimal solution runs in O(log(min(m,n))) time.

Why it failed: TLE due to using O(m+n) merge approach; fix by implementing binary search partition method with O(log(min(m,n))) complexity.

✓ Solution runs within time limit using binary search partition approach.

Practice

1. Consider the following Python code implementing the min-heap approach to find the kth smallest element in a sorted matrix. Given the matrix [[1,3],[2,4]] and k = 3, what value does the function return?

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Initialize min-heap with first elements

   Push (1,0,0) and (2,1,0) into heap.

2. Step 2: Extract elements until count == k

   Pop 1 (count=1), push 3 from row 0; pop 2 (count=2), push 4 from row 1; pop 3 (count=3), return 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Third smallest element is 3 [OK]

Hint: Trace heap pops and pushes carefully [OK]

Common Mistakes:

• Off-by-one counting of popped elements
• Returning wrong popped value
• Confusing row and column indices

2. Consider the following Python code that finds the k-th smallest number in an m x n multiplication table. What is the output when m = 3, n = 3, and k = 5?

easy

A. 6

B. 4

C. 3

D. 5

Solution

1. Step 1: Trace countLessEqual for mid=4

   For mid=4, count = sum of min(3, 4//i): i=1 -> min(3,4)=3; i=2 -> min(3,2)=2; i=3 -> min(3,1)=1; total=6 ≥ k=5, so high=4.

2. Step 2: Trace countLessEqual for mid=3

   For mid=3, count = i=1 -> 3; i=2 -> 1; i=3 -> 1; total=5 ≥ k=5, so high=3.

3. Step 3: Trace countLessEqual for mid=2

   For mid=2, count = i=1 -> 2; i=2 -> 1; i=3 -> 0; total=3 < k=5, so low=3.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Output matches expected k-th smallest number 5 [OK]

Hint: Count function caps counts per row [OK]

Common Mistakes:

• Off-by-one in counting
• Not breaking early in countLessEqual

3. You are given an array of non-negative integers and a number m. You want to split the array into m non-empty continuous subarrays such that the largest sum among these subarrays is minimized. Which algorithmic approach guarantees finding this minimal largest sum efficiently?

easy

A. Dynamic programming with memoization over all possible splits

B. Greedy approach that always splits when the current sum exceeds a fixed threshold

C. Binary search on the answer space combined with a greedy feasibility check

D. Sorting the array and using two pointers to find the minimal largest sum

Solution

1. Step 1: Understand the problem constraints

   The problem requires minimizing the largest sum among m subarrays, which is a classic optimization problem over a numeric answer space.

2. Step 2: Identify the approach that efficiently searches the answer space

   Binary search on the possible sums combined with a greedy check to verify feasibility is the standard approach that guarantees optimality and efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search on answer space is the canonical pattern for this problem [OK]

Hint: Minimize max sum -> binary search on answer space [OK]

Common Mistakes:

• Assuming greedy splitting always yields optimal solution
• Trying DP without pruning leads to exponential time
• Sorting does not help because order matters

4. The following code attempts to find the kth positive missing number from a sorted array arr. Which line contains a subtle bug that causes incorrect results for some inputs?

def findKthPositive(arr, k):
    n = len(arr)
    total_missing = arr[-1] - n
    if k > total_missing:
        return arr[-1] + (k - total_missing)
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        missing = arr[mid] - mid  # Bug here
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
    return arr[right] + (k - (arr[right] - (right + 1)))

medium

A. Line returning arr[right] + (k - (arr[right] - (right + 1)))

B. Line calculating total_missing = arr[-1] - n

C. Line updating left = mid + 1

D. Line calculating missing = arr[mid] - mid

Solution

1. Step 1: Identify the missing count formula

   The correct missing count at index mid is arr[mid] - (mid + 1), since indices are zero-based but numbers start at 1.

2. Step 2: Analyze the bug impact

   Using arr[mid] - mid undercounts missing numbers by 1, causing incorrect binary search decisions and wrong final result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct missing count formula is arr[mid] - (mid + 1) [OK]

Hint: Missing count must subtract (mid + 1), not mid [OK]

Common Mistakes:

• Off-by-one in missing count calculation
• Incorrect binary search boundary updates
• Ignoring missing numbers before first element

5. What is the time complexity of the recursive modified binary search algorithm for finding a peak element in an array of size n, and why might some candidates mistakenly think it is worse?

medium

A. O(n) because each recursive call processes a subarray of size n-1

B. O(log n) because each recursive call halves the search space

C. O(n log n) because recursion adds a log n factor to linear scanning

D. O(log n) time but O(n) space due to recursion stack

Solution

1. Step 1: Analyze recursive calls

   Each call halves the search space, so number of calls is O(log n).

2. Step 2: Confirm work per call

   Each call does O(1) work (simple comparisons), so total time is O(log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Halving search space leads to logarithmic time [OK]

Hint: Halving input size -> O(log n) time [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming linear scan inside recursion
• Thinking recursion multiplies complexity