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. You need to ship packages within a given number of days. Each package has a weight, and you must ship packages in order without splitting any package. You want to find the minimum ship capacity to ship all packages within the deadline. Which algorithmic approach guarantees finding the optimal ship capacity efficiently?

easy

A. Greedy approach that assigns packages to days until capacity is reached, then moves to next day without binary search

B. Dynamic programming to find the minimum capacity by exploring all subsets of packages and days

C. Sorting packages and using a two-pointer technique to assign packages to days

D. Binary search on the answer space (capacity) combined with a feasibility check to verify if shipping within days is possible

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding a minimum capacity that allows shipping all packages in order within a fixed number of days.

2. Step 2: Recognize the pattern

   Binary searching the capacity (answer space) and checking feasibility is the optimal approach because capacity ranges between max package weight and sum of all weights, and feasibility can be checked in linear time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search on answer space is classic for optimization with feasibility checks [OK]

Hint: Binary search on capacity range solves this optimally [OK]

Common Mistakes:

• Thinking greedy alone finds minimal capacity
• Confusing DP with subset sums
• Using two pointers without sorting relevance

2. You are given a sorted array and a target number x. The task is to find k elements closest to x in the array, with ties broken by choosing the smaller elements first. Which of the following approaches guarantees an optimal solution with logarithmic search complexity on the array?

easy

A. Use a greedy approach by iteratively picking the closest element to x until k elements are chosen.

B. Use dynamic programming to compute the minimum distance sum for all windows of size k and pick the minimum.

C. Perform a binary search to find the left boundary of the window of size k that contains the closest elements to x.

D. Use a two-pointer sliding window starting from both ends of the array and shrink towards the center until k elements remain.

Solution

1. Step 1: Understand problem constraints

   The array is sorted, and we want k closest elements to x with tie-breakers favoring smaller elements.

2. Step 2: Identify approach with logarithmic complexity

   Binary search on the left boundary of the window of size k efficiently narrows down the candidate window in O(log(n-k)) time, guaranteeing optimality.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search exploits sorted order and window size constraints [OK]

Hint: Binary search on window boundaries exploits sorted array [OK]

Common Mistakes:

• Assuming greedy selection always yields optimal window
• Using DP unnecessarily increasing complexity
• Two-pointer approach is linear, not logarithmic

3. You are given a sorted array and a target value. You need to find the index where the target should be inserted to maintain the sorted order. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that inserts the target at the first position where the next element is larger

B. Linear scan from the start to find the first element greater than or equal to the target

C. Dynamic programming that builds solutions for subproblems of smaller arrays

D. Binary search that repeatedly halves the search space to find the correct insertion index

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so searching can be optimized by halving the search space instead of scanning linearly.

2. Step 2: Identify the algorithm that efficiently finds insertion index

   Binary search divides the array repeatedly, guaranteeing O(log n) time, which is optimal compared to linear or DP approaches.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search is the classic approach for sorted array search problems [OK]

Hint: Sorted array + insertion -> binary search [OK]

Common Mistakes:

• Assuming greedy insertion is always optimal
• Confusing DP with binary search
• Using linear scan despite sorted input

4. The following code attempts to find the k-th smallest number in an m x n multiplication table. Which line contains a subtle bug that can cause incorrect results for large inputs?

medium

A. Line 4: count = 0

B. Line 6: count += x // i # missing min with n

C. Line 8: if count >= k:

D. Line 13: mid = (low + high) // 2

Solution

1. Step 1: Identify counting logic

   The counting function must cap counts per row by n, since each row has only n elements.

2. Step 2: Analyze line 6

   Line 6 adds x // i without min(n, x // i), causing overcounting when x // i > n, leading to incorrect binary search decisions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bug causes wrong counts and incorrect final answer [OK]

Hint: Count per row capped by n to avoid overcounting [OK]

Common Mistakes:

• Forgetting min(n, x//i) in counting
• Incorrect mid calculation

5. The following code attempts to find the maximum minimum distance to place m balls in position. Identify the bug that causes incorrect results or infinite loops.

medium

A. Not stopping early in can_place after placing all balls

B. Incorrect binary search boundaries: low should start at 0

C. Returning result before binary search loop ends

D. Line missing position.sort() before feasibility check

Solution

1. Step 1: Check sorting necessity

   The feasibility check assumes positions are sorted to place balls greedily. Missing position.sort() breaks this assumption.

2. Step 2: Consequences of missing sort

   Without sorting, the greedy check may fail to place balls correctly, causing wrong feasibility results and incorrect final answer.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting is essential before greedy feasibility check [OK]

Hint: Positions must be sorted before greedy feasibility check [OK]

Common Mistakes:

• Forgetting to sort positions
• Incorrect binary search boundaries causing infinite loops