Median of Two Sorted Arrays of Different Sizes: Brute and Better Approaches

1. Problem Statement & Foundational Context

Finding the median of two sorted arrays is a fundamental algorithmic challenge in Data Structures and Algorithms (DSA). You are given two sorted arrays, $A$ and $B$, which may have equal or completely different sizes ($N_1$ and $N_2$).

The objective is to find their combined median. The crucial characteristic that makes this solvable efficiently is that both input arrays are already sorted.

What is a Median?

The median is the middle value separating the higher half from the lower half of a data set.

• Odd Total Elements ($N = N_1 + N_2$ is odd): There is a single exact middle element.
  • Example: Combined elements [1, 2, 3, 3, 4] ($N = 5$). The median is the element at index $\lfloor 5 / 2 \rfloor = 2$, which is 3.
• Even Total Elements ($N = N_1 + N_2$ is even): There is no single middle element. The median is the average of the two middle elements.
  • Example: Combined elements [1, 2, 3, 3, 4, 6, 7, 10, 12, 15] ($N = 10$). The middle elements are at indices $N/2 - 1$ (index $4$, value 4) and $N/2$ (index $5$, value 6). The median is $(4 + 6) / 2 = 5.0$.

2. Core Mental Model & Analogy

Real-Life Analogy: Imagine two distinct lines of people standing outside two different ticket counters, where every person in both lines is already arranged strictly by height (ascending order). You are tasked with finding the exact person (or the average height of the two middle people) who would stand precisely in the middle if both lines were merged into a single orderly queue.

Instead of building a massive holding room to merge everyone physically (Brute Force), a smarter approach is to simply walk down both lines simultaneously with two pointers, counting people off one by one until you reach the exact middle position(s) you care about.

3. The Naive Approach: Merge Sort Technique (Brute Force)

The most intuitive, brute-force way to solve this problem is to replicate the merging step of Merge Sort. Since both arrays are already sorted, you can compare elements from the front of both arrays and deposit the smaller element into a third, newly created array.

Step-by-Step Execution

1. Initialize an empty third array, array3.
2. Set two pointers, i = 0 (for Array 1) and j = 0 (for Array 2).
3. Compare elements at array1[i] and array2[j]. Append the smaller element to array3 and increment that pointer.
4. Once one array is exhausted, dump all remaining elements of the other array into array3.
5. Calculate the median directly from array3 using its total length $N = N_1 + N_2$.

Brute Force Pseudo-Code

def findMedianSortedArrays_Brute(array1, array2):
    N1 = len(array1)
    N2 = len(array2)
    array3 = []
    i, j = 0, 0
    
    # Merge two sorted arrays into array3
    while i < N1 and j < N2:
        if array1[i] < array2[j]:
            array3.append(array1[i])
            i += 1
        else:
            array3.append(array2[j])
            j += 1
            
    while i < N1:
        array3.append(array1[i])
        i += 1
        
    while j < N2:
        array3.append(array2[j])
        j += 1
        
    N = N1 + N2
    if N % 2 == 1:
        return float(array3[N // 2])
    else:
        return (array3[N // 2] + array3[N // 2 - 1]) / 2.0

Complexity Analysis of Brute Force

• Time Complexity: $O(N_1 + N_2)$ because we visit every single element across both input arrays during the merge phase.
• Space Complexity: $O(N_1 + N_2)$ because we allocate a brand new auxiliary array (array3) to store all merged elements.

Production Pitfall: In online judges (like LeetCode), this solution receives a Time Limit Exceeded (TLE) or Memory Limit Exceeded on massive datasets because storing all elements introduces unnecessary memory overhead.

4. Transitioning to Space Optimization

If you examine the brute-force solution closely, you realize a profound truth: We do not actually need all the elements stored in memory.

To find the median, we only care about specific target indices:

• If $N$ is even, we need the values at indices $\frac{N}{2}$ and $\frac{N}{2} - 1$.
• If $N$ is odd, we need the value at index $\frac{N}{2}$.

Instead of allocating an auxiliary array of size $N_1 + N_2$, we can eliminate storage entirely by using an index tracker (count) and two pointer variables (element1 and element2) to catch the required middle values on the fly.

5. The Better Approach: Pointer Simulation & Space Optimization

We simulate the merge process without actually storing any elements. We track our position in the hypothetical merged array using a count variable starting from 0.

Identifying Target Indices

Let $N = N_1 + N_2$.

• index2 = N // 2
• index1 = (N // 2) - 1 (used only if $N$ is even)

As our pointers (i and j) advance through array1 and array2, our count increments. Whenever count matches index1 or index2, we capture the current element into element1 or element2.

Conceptual Pointer Flow Walkthrough

6. Complete Implementation of the Better Approach

Here is the robust, space-optimized implementation reflecting the pointer simulation logic:

#include <vector>
#include <algorithm>

class Solution {
public:
    double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        int n = n1 + n2;
        
        // Define target indices
        int index2 = n / 2;
        int index1 = index2 - 1;
        
        int count = 0;
        int element1 = -1, element2 = -1;
        
        int i = 0, j = 0;
        
        // Traverse both arrays like merge sort
        while (i < n1 && j < n2) {
            int currentVal;
            if (nums1[i] < nums2[j]) {
                currentVal = nums1[i];
                i++;
            } else {
                currentVal = nums2[j];
                j++;
            }
            
            if (count == index1) element1 = currentVal;
            if (count == index2) element2 = currentVal;
            count++;
        }
        
        // Flush remaining elements from nums1 if any
        while (i < n1) {
            int currentVal = nums1[i];
            i++;
            if (count == index1) element1 = currentVal;
            if (count == index2) element2 = currentVal;
            count++;
        }
        
        // Flush remaining elements from nums2 if any
        while (j < n2) {
            int currentVal = nums2[j];
            j++;
            if (count == index1) element1 = currentVal;
            if (count == index2) element2 = currentVal;
            count++;
        }
        
        // Compute final median based on parity
        if (n % 2 == 1) {
            return static_cast<double>(element2);
        } else {
            return (double)(element1 + element2) / 2.0;
        }
    }
};

7. Comparative Synthesis: Brute vs. Better Approach

8. Summary and Key Takeaways

• Importance of Sorted Inputs: The sorted nature of both input arrays allows linear-time merging without needing full sorting algorithms like Quicksort or Mergesort.
• Space Reduction Insight: You never need to store all merged elements to find a median; tracking indices dynamically via pointers achieves $O(1)$ space complexity.
• Parity Handling: Always check whether the combined length ($N_1 + N_2$) is odd or even to determine whether to return a single middle value or the average of two middle values.
• Type Casting Caution: When dividing integer sums in languages like C++ or Java to find a median, remember to cast values to double (e.g., / 2.0) to prevent integer truncation bugs.
• Next Evolutionary Step: While the better approach reduces space to $O(1)$, its time complexity remains $O(N_1 + N_2)$. To achieve optimal logarithmic time complexity $O(\log(\min(N_1, N_2)))$, binary search on partitions must be applied in subsequent advanced approaches.