NUHMAN.com

Introduction

The "Median of Two Sorted Arrays" is one of the most challenging problems on LeetCode. It requires a deep understanding of binary search and efficient problem-solving techniques. In this article, we’ll tackle LeetCode 4 using an O(log(min(m, n))) solution in Go, with a step-by-step explanation.

Problem Statement

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example

go

Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
Explanation: The combined array is [1, 2, 3], and the median is 2.
go

Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 2.5
Explanation: The combined array is [1, 2, 3, 4], and the median is (2 + 3)/2 = 2.5.

Brute Force Approach (O(m + n))

You could merge both arrays and then find the median. But this doesn’t meet the time complexity requirement of O(log (m+n)).

Optimized Approach: Binary Search on the Shorter Array

We use binary search to partition both arrays in a way that all elements on the left are less than or equal to those on the right.

Key Concepts:

• Median splits the merged array into two halves of equal length.
• We need to find the correct partition point using binary search.

Steps:

1. Ensure nums1 is the shorter array.
2. Binary search on nums1:

• Partition both arrays at i and j = (m + n + 1)/2 - i

1. Find maxLeft and minRight for both partitions.
2. If maxLeft <= minRight:

• If total length is even, median = average of maxLeft and minRight.
• If odd, median = maxLeft.

1. If not, adjust binary search range.

Go Implementation

go

package main

import (
    "fmt"
    "math"
)

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    // Ensure nums1 is the smaller array
    if len(nums1) > len(nums2) {
        return findMedianSortedArrays(nums2, nums1)
    }

    x, y := len(nums1), len(nums2)
    low, high := 0, x

    for low <= high {
        partitionX := (low + high) / 2
        partitionY := (x + y + 1) / 2 - partitionX

        maxLeftX := math.Inf(-1)
        if partitionX != 0 {
            maxLeftX = float64(nums1[partitionX-1])
        }

        minRightX := math.Inf(1)
        if partitionX != x {
            minRightX = float64(nums1[partitionX])
        }

        maxLeftY := math.Inf(-1)
        if partitionY != 0 {
            maxLeftY = float64(nums2[partitionY-1])
        }

        minRightY := math.Inf(1)
        if partitionY != y {
            minRightY = float64(nums2[partitionY])
        }

        if maxLeftX <= minRightY && maxLeftY <= minRightX {
            if (x+y)%2 == 0 {
                return (math.Max(maxLeftX, maxLeftY) + math.Min(minRightX, minRightY)) / 2
            } else {
                return math.Max(maxLeftX, maxLeftY)
            }
        } else if maxLeftX > minRightY {
            high = partitionX - 1
        } else {
            low = partitionX + 1
        }
    }

    panic("Input arrays are not sorted")
}

func main() {
    nums1 := []int{1, 3}
    nums2 := []int{2}
    fmt.Printf("Median: %.1f\n", findMedianSortedArrays(nums1, nums2))

    nums1 = []int{1, 2}
    nums2 = []int{3, 4}
    fmt.Printf("Median: %.1f\n", findMedianSortedArrays(nums1, nums2))
}

Time and Space Complexity

• Time Complexity: O(log(min(m, n))) — binary search on the shorter array.
• Space Complexity: O(1) — constant space.

Key Takeaways

• This is a classic divide-and-conquer problem disguised as a median-finding task.
• The key trick is to partition arrays correctly using binary search.
• Always binary search on the smaller array to reduce complexity.