Median Mastery – Sorted Arrays, Sorted Mind

 Cutting Right Through the Middle – Finding the Median of Two Sorted Arrays

We’re diving into one of the most talked-about problems in DSA interviews – and not just because it’s labeled “Hard” on LeetCode. The Median of Two Sorted Arrays pushes us to go beyond brute force and embrace optimized divide-and-conquer techniques.

Problem Recap

You’re given two sorted arrays nums1 and nums2. You need to return the median of the two sorted arrays. 

The best data structure for solving it (and why!)

Arrays are the core structure here – no need for fancy DS. But what matters is how you access and partition them efficiently. The optimized approach uses the idea of binary search on partitions, which works perfectly with sorted arrays.

Different approaches – from brute force to optimized solutions

Approach 1: Merge and Find (Brute Force)

Just like merging in merge sort. Combine the arrays, sort them (or just merge them properly), and find the median.


public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] merged = new int[nums1.length + nums2.length];
    int i = 0, j = 0, k = 0;

    while (i < nums1.length && j < nums2.length) {
        merged[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
    }
    while (i < nums1.length) merged[k++] = nums1[i++];
    while (j < nums2.length) merged[k++] = nums2[j++];

    int n = merged.length;
    if (n % 2 == 0) {
        return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
    } else {
        return merged[n / 2];
    }
}

Approach 2: Binary Search on Shorter Array (Optimized – O(log(min(m,n))))

Here comes the brainy bit. Instead of merging, we binary search the partition point in the smaller array and determine if it satisfies the median condition using values from both arrays.


public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int x = nums1.length;
    int y = nums2.length;
    int low = 0, high = x;

    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (x + y + 1) / 2 - partitionX;

        int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
        int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];

        int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
        int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 == 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }

    throw new IllegalArgumentException("Input arrays are not sorted properly");
}

⚠️Common mistakes & pitfalls to avoid

  • Not ensuring nums1 is the smaller array in the optimized approach – binary search should always be done on the shorter one.

  • Edge cases like one array being empty, or arrays of very different sizes.

  • Off-by-one errors when calculating partitions or accessing array indices.

📊Time & Space complexity analysis

Approach 1: Merge and Find

  • Time: O(m + n)

  • Space: O(m + n)

Approach 2: Binary Search Partition

  • Time: O(log(min(m, n)))

  • Space: O(1)

🌍Real-world applications 

  • Statistics engines: Median is a core metric in descriptive stats.

  • Real-time analytics: When dealing with streaming data from two sorted sources (like logs or IoT sensors).

  • Financial data: Median salary or transaction data across datasets.


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Zero Array After Queries

Zero Array After Queries You are given an integer array nums and a list of queries, where each query is a pair [li, ri] representing a range. Each query allows you to decrement any subset of elements in the range [li, ri] by 1. Your task is to determine if it is possible to make every element in nums equal to zero after applying all queries in order . Example Input: nums = [ 1 , 0 , 1 ] queries = [[0, 2]] Output: true Explanation: We can select indices 0 and 2 and decrement both by 1 to obtain [0, 0, 0] . Best Data Structure for the Job We are working with multiple range updates and need to evaluate coverage over indices. The best choice here is the difference array combined with a prefix sum . It allows efficient range additions and helps track how many times each index is affected by the queries. Different Approaches Approach 1: Brute Force This naive method iterates over every index for every query and performs the decrement operations directly. class Solution {...
Read more