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 function implementing space-optimized bottom-up DP for edit distance. What is the value of current[1] after the first iteration of the inner loop when calling minDistance("abc", "ac") during the iteration where i = 2?

easy

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Identify iteration i=2 corresponds to last character 'c' in "abc"

   At i=2, word1[i] = 'c'. The inner loop runs j=1 to 0 for word2="ac".

2. Step 2: Compute current[1] when j=1 (word2[1] = 'c')

   Since word1[2] == word2[1] ('c' == 'c'), current[1] = next_row[2]. Initially, next_row = [2,1,0], so next_row[2] = 0.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matching chars yield current[j] = next_row[j+1] = 0 [OK]

Hint: Matching chars copy diagonal DP value [OK]

Common Mistakes:

• Off-by-one indexing in j or i
• Confusing current and next_row arrays

2. You are given an undirected graph with n nodes. You need to find the shortest path length that visits every node at least once. Which algorithmic approach guarantees finding the optimal solution efficiently for this problem?

easy

A. Simple DFS traversal with backtracking to explore all paths

B. Greedy algorithm that always moves to the nearest unvisited node

C. Dynamic programming on subsets without BFS, enumerating all permutations

D. Bidirectional BFS with state compression using bitmasks to track visited nodes

Solution

1. Step 1: Understand problem constraints

   The problem requires visiting all nodes with the shortest path, which is a variant of the Traveling Salesman Problem (TSP) on an unweighted graph.

2. Step 2: Identify suitable algorithm

   Greedy and simple DFS approaches do not guarantee shortest paths and are inefficient. DP on subsets is correct but has O(n*2^n) complexity. Bidirectional BFS with bitmask state compression reduces complexity to O(n*2^(n/2)), making it optimal and efficient.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask BFS tracks visited nodes efficiently and bidirectional search halves the state space [OK]

Hint: Bitmask + bidirectional BFS optimizes shortest path visiting all nodes [OK]

Common Mistakes:

• Assuming greedy nearest neighbor always finds shortest path
• Using DFS without pruning leads to exponential blowup
• Confusing DP on subsets with simpler DP variants

3. What is the worst-case time complexity of the optimal backtracking solution for the Expression Add Operators problem, given a numeric string of length n?

medium

A. O(n^3) due to nested loops and substring parsing

B. O(2^n) because each digit can either be concatenated or separated by an operator

C. O(4^n) because each digit can be followed by 4 choices: +, -, *, or no operator (concatenate)

D. O(3^n) since only three operators are inserted between digits

Solution

1. Step 1: Identify branching factor per digit

   At each digit (except the first), there are 4 choices: add '+', '-', '*', or concatenate (no operator).

2. Step 2: Calculate total combinations

   With n digits, the number of expressions is roughly 4^(n-1), which is O(4^n) in worst case.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   4 choices per digit lead to exponential 4^n growth [OK]

Hint: Count operator choices plus concatenation per digit [OK]

Common Mistakes:

• Confusing 3 operators only, ignoring concatenation
• Assuming polynomial complexity

4. Identify the bug in the following MedianFinder code snippet that causes incorrect median calculation or runtime errors.

medium

A. Line returning median when small_size > large_size

B. Line balancing heaps when small_size > large_size + 1

C. Line with condition: if not self.small or num <= self.small[0]:

D. Line balancing heaps when large_size > small_size

Solution

1. Step 1: Examine heap insertion condition

   small is a max heap simulated by negating values, so top is -small[0]. Comparing num to self.small[0] (positive) is incorrect.

2. Step 2: Correct condition

   Should compare num <= -self.small[0] to correctly decide which heap to push into.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Negation missing in comparison causes wrong heap insertion [OK]

Hint: Remember to negate values when simulating max heap in Python [OK]

Common Mistakes:

• Forgetting to negate values in comparisons
• Not balancing heaps after insertion
• Incorrect median calculation when heaps unbalanced

5. What is the time complexity of the bitmask backtracking solution for the N-Queens problem, and why is it not simply O(n^n)?

medium

A. O(n^n) because each row tries all columns independently

B. O(2^n) because bitmasking iterates over all subsets of columns

C. O(n!) because each queen placement reduces available columns and pruning avoids invalid states

D. O(n^2) because the board is of size nxn and each cell is checked

Solution

1. Step 1: Understand pruning effect on search space

   Each queen placed reduces available columns, so permutations of columns are tried, not all combinations.

2. Step 2: Recognize factorial complexity

   Backtracking tries permutations of n columns for n rows, leading to O(n!) complexity, not exponential or polynomial.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Pruning reduces search to permutations, not all subsets [OK]

Hint: N-Queens backtracking explores permutations -> O(n!) [OK]

Common Mistakes:

• Confusing subsets (2^n) with permutations (n!)
• Assuming polynomial due to board size
• Ignoring pruning effect